We consider the notion of a constant length queue automaton --- i.e., a traditional queue automaton with a built-in constant limit on the length of its queue --- as a formalism for representing regular languages. We show that the descriptional power of constant length queue automata greatly 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. Finally, we investigate the size cost of implementing boolean language operations on deterministic and nondeterministic constant length queue automata.

The descriptional power of queue automata of constant length / S. Jakobi, K. Meckel, C. Mereghetti, B.S. Palano. - In: ACTA INFORMATICA. - ISSN 0001-5903. - 58:4(2021 Aug), pp. 335-356. [10.1007/s00236-021-00398-7]

The descriptional power of queue automata of constant length

Carlo Mereghetti;Beatrice Palano
2021-08

Abstract

We consider the notion of a constant length queue automaton --- i.e., a traditional queue automaton with a built-in constant limit on the length of its queue --- as a formalism for representing regular languages. We show that the descriptional power of constant length queue automata greatly 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. Finally, we investigate the size cost of implementing boolean language operations on deterministic and nondeterministic constant length queue automata.
Deterministic and nondeterministic queue and pushdown automata; Straight line programs
Settore INF/01 - Informatica
19-lug-2021
ACTA INFORMATICA
Article (author)
File in questo prodotto:
File Dimensione Formato  
AI.KUTRIB.pdf

accesso aperto

329.49 kB Adobe PDF Visualizza/Apri
Jakobi2021_Article_TheDescriptionalPowerOfQueueAu.pdf

accesso aperto

434.8 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/858670
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact