Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Safety Is not a Restriction at Level 2 for String Languages
verfasst von : K. Aehlig, J. G. de Miranda, C. -H. L. Ong
Erschienen in: Foundations of Software Science and Computational Structures
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Recent work by Knapik, Niwiński and Urzyczyn (in FOSSACS 2002) has revived interest in the connexions between higher-order grammars and higher-order pushdown automata. Both devices can be viewed as definitions for term trees as well as string languages. In the latter setting we recall the extensive study by Damm (1982), and Damm and Goerdt (1986). There it was shown that a language is accepted by a level-
n
pushdown automaton if and only if the language is generated by a
safe
level-
n
grammar. We show that at level 2 the safety assumption may be removed. It follows that there are no
inherently
unsafe string languages at level 2.