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. Finally, a different simulation shows that also the conversion of deterministic constant-height pushdown automata into deterministic 1-limited automata costs polynomial.
Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata / B. Guillon, G. Pighizzini, L. Prigioniero. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 31:8(2020 Dec), pp. 1133-1157.
|Titolo:||Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata|
PRIGIONIERO, LUCA (Corresponding)
|Parole Chiave:||context-free grammars; Descriptional complexity; limited automata; non-self-embedding grammars; pushdown automata; regular languages|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||dic-2020|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1142/S0129054120420071|
|Appare nelle tipologie:||01 - Articolo su periodico|