Non-self-embedding grammars, constant-height pushdown automata and 1-limited automata are restrictions of context-free grammars, pushdown automata and Turing machines, respectively. All of them characterize the class of regular languages. There is a double size exponential gap from each of these models to deterministic finite automata. Non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Moreover, there exists a polynomial size simulation by 1-limited automata. In contrast, the converse transformation costs exponential.
On some succinct representations of regular languages : extended abstract / B. Guillon, G. Pighizzini, L. Prigioniero (CEUR WORKSHOP PROCEEDINGS). - In: Italian Conference on Theoretical Computer Science / [a cura di] A. Aldini, M. Bernardo. - [s.l] : CEUR-WS, 2018. - pp. 203-207 (( Intervento presentato al 19. convegno Italian Conference on Theoretical Computer Science tenutosi a Urbino nel 2018.
On some succinct representations of regular languages : extended abstract
B. Guillon
;G. Pighizzini
;L. Prigioniero
2018
Abstract
Non-self-embedding grammars, constant-height pushdown automata and 1-limited automata are restrictions of context-free grammars, pushdown automata and Turing machines, respectively. All of them characterize the class of regular languages. There is a double size exponential gap from each of these models to deterministic finite automata. Non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Moreover, there exists a polynomial size simulation by 1-limited automata. In contrast, the converse transformation costs exponential.File | Dimensione | Formato | |
---|---|---|---|
paper19.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
414.29 kB
Formato
Adobe PDF
|
414.29 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.