We introduce and study the notion of constant length queue automata, as a formalism for representing regular languages. We show that their descriptional power outperforms that of traditional finite state automata, of constant height pushdown automata, and of straight line programs for regular expressions, by providing optimal exponential and double-exponential size gaps. Moreover, we prove that constant height pushdown automata can be simulated by constant length queue automata paying only by a linear size increase, and that removing nondeterminism in constant length queue automata requires an optimal exponential size blow-up, against the optimal double-exponential cost for determinizing constant height pushdown automata.
Queue automata of constant length / S. Jakobi, K. Meckel, C. Mereghetti, B. Palano (LECTURE NOTES IN COMPUTER SCIENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] H. Jurgensen, R. Reis. - Berlin : Springer, 2013. - ISBN 9783642393099. - pp. 124-135 (( Intervento presentato al 15. convegno International Workshop on Descriptional Complexity of Formal Systems (DCFS) tenutosi a London nel 2013 [10.1007/978-3-642-39310-5_13].
Queue automata of constant length
C. Mereghetti;B. PalanoUltimo
2013
Abstract
We introduce and study the notion of constant length queue automata, as a formalism for representing regular languages. We show that their descriptional power outperforms that of traditional finite state automata, of constant height pushdown automata, and of straight line programs for regular expressions, by providing optimal exponential and double-exponential size gaps. Moreover, we prove that constant height pushdown automata can be simulated by constant length queue automata paying only by a linear size increase, and that removing nondeterminism in constant length queue automata requires an optimal exponential size blow-up, against the optimal double-exponential cost for determinizing constant height pushdown automata.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
219.6 kB
Formato
Adobe PDF
|
219.6 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.