We introduce and study the model of deterministic input-driven queue automata. On such devices, the input letters uniquely determine the operations on the memory store which is organized as a queue. In particular, we consider the case where only a finite number of turns on the queue is allowed. The resulting language families share with regular languages many desirable properties. We show that emptiness and several other problems are decidable. Furthermore, we investigate closure under Boolean operations. The existence of an infinite and tight hierarchy depending on the number of turns is also proved.
Deterministic input-driven queue automata : finite turns, decidability, and closure properties / M. Kutrib, A. Malcher, C. Mereghetti, B. Palano, M. Wendlandt. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 578(2015 May 03), pp. 58-71. [10.1016/j.tcs.2015.01.012]
Deterministic input-driven queue automata : finite turns, decidability, and closure properties
C. Mereghetti;B. PalanoPenultimo
;
2015
Abstract
We introduce and study the model of deterministic input-driven queue automata. On such devices, the input letters uniquely determine the operations on the memory store which is organized as a queue. In particular, we consider the case where only a finite number of turns on the queue is allowed. The resulting language families share with regular languages many desirable properties. We show that emptiness and several other problems are decidable. Furthermore, we investigate closure under Boolean operations. The existence of an infinite and tight hierarchy depending on the number of turns is also proved.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
466.62 kB
Formato
Adobe PDF
|
466.62 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.