An Approach to Infinite Term Traversal in DCGs

This paper describes a practical approach for detecting, traversing and representing cyclic terms in definite clause grammars. Our goal is to make a wider range of this formalism executable, without overload for non-cyclic structures. Unlike preceding approaches, our proposal avoids backtracking and changing of values in variables, increasing computational efficiency in a dynamic programming frame based on the logical push-down automaton model.

Keywords: Definite Clause Grammar, Dynamic Programming, Logical Push-Down Automaton, Cyclic Term.