Conference paper

Publication year: 2015

Pages: 58-71

Journal: Theoretical Computer Science

Volume number: 578

ISSN: 0304-3975

eISSN: 1879-2294

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

Conference: 18th CIAA International Conference

Publisher: 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 Citation style: 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 Citation style: 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