View Related Documents

Abstract

Syntactical graphs are representations of derivations of arbitrary grammars. The height of syntactical graphs is introduced here as a complexity measure. It is shown that polynomial height-bounded e-free grammars are equivalent to polynomial time-bounded nondeterministic Turing machines, and that polynomial height-bounded arbitrary grammars are equivalent to polynomial space-bounded Turing machines. Furthermore, context-free languages are linear height-bounded and regular languages are logarithmic height-bounded, even for context-free grammars.

Fulltext Preview

Image of the first page of the fulltext document