Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding grammars to deterministic finite automata is known. The same size gap is also known from constant-height pushdown automata and 1-limited automata to deterministic finite automata. Constant-height pushdown automata and 1-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Furthermore, a polynomial size simulation by 1-limited automata is presented. However, the converse transformation is proved to cost exponential.
Non-self-embedding grammars, constant-height pushdown automata, and limited automata / B. Guillon, G. Pighizzini, L. Prigioniero (LECTURE NOTES IN COMPUTER SCIENCE). - In: Implementation and Application of Automata / [a cura di] C. Câmpeanu. - [s.l] : Springer Verlag, 2018. - ISBN 9783319948119. - pp. 186-197 (( Intervento presentato al 23. convegno International Conference on Implementation and Application of Automata tenutosi a Charlottetown nel 2018 [10.1007/978-3-319-94812-6_16].
Non-self-embedding grammars, constant-height pushdown automata, and limited automata
B. Guillon;G. Pighizzini;L. Prigioniero
2018
Abstract
Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding grammars to deterministic finite automata is known. The same size gap is also known from constant-height pushdown automata and 1-limited automata to deterministic finite automata. Constant-height pushdown automata and 1-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Furthermore, a polynomial size simulation by 1-limited automata is presented. However, the converse transformation is proved to cost exponential.File | Dimensione | Formato | |
---|---|---|---|
nse-pda.pdf
accesso riservato
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
334.92 kB
Formato
Adobe PDF
|
334.92 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.