Safety is not a restriction at level 2 for string languages
K. Aehlig‚ J. G. de Miranda and C.−H. L. Ong
Abstract
Recent work by Knapik, Niwinski and Urzczyn [KNU02] 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 [Dam82], and Damm and Goerdt [DG86]. There it was shown that the language of a level-n higher-order grammar is accepted by a level-n higher-order pushdown automaton subject to the restriction of derived types, more recent rebranded as safety. We show that at level 2, if a string language is generated by an unsafe grammar, there is a (level-2, non-deterministic) safe grammar that generates the same language. Thus safety is not a restriction for level-2 string languages.
Details
| Institution |
Oxford University Computing Laboratory |
| Month |
October |
| Number |
RR−04−23 |
| Year |
2004 |
Links
Related pages
|
People |