Konferenzpaper

Jahr der Veröffentlichung: 2015

Seiten: 58-71

Zeitschrift: Theoretical Computer Science

Bandnummer: 578

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2015.01.012

Konferenz: 18th CIAA International Conference

Verlag: Elsevier

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. (C) 2015 Elsevier B.V. All rights reserved.

Harvard-Zitierstil: Kutrib, M., Malcher, A., Mereghetti, C., Palano, B. and Wendlandt, M. (2015) Deterministic input-driven queue automata: Finite turns, decidability, and closure properties, Theoretical Computer Science, 578, pp. 58-71. https://doi.org/10.1016/j.tcs.2015.01.012

APA-Zitierstil: Kutrib, M., Malcher, A., Mereghetti, C., Palano, B., & Wendlandt, M. (2015). Deterministic input-driven queue automata: Finite turns, decidability, and closure properties. Theoretical Computer Science. 578, 58-71. https://doi.org/10.1016/j.tcs.2015.01.012