Paper Info
Title
Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, And Limited Automata
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. Finally, a different simulation shows that also the conversion of deterministic constant-height pushdown automata into deterministic 1-limited automata costs polynomial.
Year
DOI
Venue
2020
10.1142/S0129054120420071
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
DocType
Volume
Descriptional complexity, regular languages, limited automata, pushdown automata, non-self-embedding grammars, context-free grammars
Journal
31
Issue
ISSN
Citations 
8
0129-0541
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Bruno Guillon121.39
Giovanni Pighizzini200.34
Luca Prigioniero302.03