Displaying similar documents to “A constructive proof of equivalence of formalism of DCG's with the formalism of type 0 phrase-structure grammars.”

On context-free rewriting with a simple restriction and its computational completeness

Tomáš Masopust, Alexander Meduna (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper discusses context-free rewriting systems in which there exist two disjoint finite sets of rules, and a symbol, referred to as a condition of applicability, is attached to each rule in either of these two sets. In one set, a rule with a symbol attached to it is applicable if the attached symbol occurs in the current rewritten string while in the other set, such a rule is applicable if the attached symbol does not occur there. The present paper demonstrates that these rewriting...