We introduce and study the model of diving queue automata which are basically finite automata equipped with a storage medium that is organized as a queue. Additionally, two queue heads are provided at both ends of the queue that can move in a read-only mode inside the queue. In particular, we consider suitable time constraints and the case where only a finite number of turns on the queue is allowed. As one main result we obtain a proper queue head hierarchy, that is, two heads are better than one head, and one head is better than no head. Moreover, it is shown that the model with one queue head, finitely many turns, and no time constraints as well as the model with two queue heads, possibly infinitely many turns, and time constraints is captured by P and has a P-complete membership problem. We obtain also that a subclass of the model with two queue heads is already captured by logarithmic space. Finally, we consider decidability questions and it turns out that almost nothing is decidable for the model with two queue heads, whereas we obtain that at least emptiness and finiteness are decidable for subclasses of the model with one queue head.
DOI : 10.1051/ita/2018009
Mots clés : Queue automata, logspace Turing machines, formal languages, decidability questions
@article{ITA_2018__52_2-3-4_89_0,
author = {Beier, Simon and Kutrib, Martin and Malcher, Andreas and Wendlandt, Matthias},
editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
title = {Diving into the queue},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {89--110},
publisher = {EDP-Sciences},
volume = {52},
number = {2-3-4},
year = {2018},
doi = {10.1051/ita/2018009},
mrnumber = {3915303},
zbl = {1423.68243},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2018009/}
}
TY - JOUR AU - Beier, Simon AU - Kutrib, Martin AU - Malcher, Andreas AU - Wendlandt, Matthias ED - Bordihn, Henning ED - Nagy, Benedek ED - Vaszil, György TI - Diving into the queue JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 89 EP - 110 VL - 52 IS - 2-3-4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2018009/ DO - 10.1051/ita/2018009 LA - en ID - ITA_2018__52_2-3-4_89_0 ER -
%0 Journal Article %A Beier, Simon %A Kutrib, Martin %A Malcher, Andreas %A Wendlandt, Matthias %E Bordihn, Henning %E Nagy, Benedek %E Vaszil, György %T Diving into the queue %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 89-110 %V 52 %N 2-3-4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2018009/ %R 10.1051/ita/2018009 %G en %F ITA_2018__52_2-3-4_89_0
Beier, Simon; Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias. Diving into the queue. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 89-110. doi : 10.1051/ita/2018009. http://www.numdam.org/articles/10.1051/ita/2018009/
[1] , Indexed grammars – an extension of context-free grammars. J. ACM 15 (1968) 647–671 | DOI | MR | Zbl
[2] , Nested stack automata. J. ACM 16 (1969) 383–406 | DOI | MR | Zbl
[3] , On the intersection of stacks and queues. Theor. Comput. Sci. 58 (1988) 69–80 | DOI | MR | Zbl
[4] and , Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141 (1998) 1–36 | DOI | MR | Zbl
[5] , , and , QRT FIFO automata, breadth-first grammars and their relations. Theor. Comput. Sci. 85 (1991) 171–203 | DOI | MR | Zbl
[6] , Context-free grammars and pushdown storage. Vol. 65 of Quarterly Progress Report. MIT Research Laboratory of Electronics, Massachusetts (1962) 187–194
[7] , A shrinking lemma for indexed languages. Theor. Comput. Sci. 163 (1996) 277–281 | DOI | MR | Zbl
[8] , and , One-way stack automata. J. ACM 14 (1967) 389–418 | DOI | MR | Zbl
[9] , and , Stack automata and compiling. J. ACM 14 (1967) 172–201 | DOI | MR | Zbl
[10] , Context-free languages and Turing machine computations, in vol. of 19 Proc. Symposia in Applied Mathematics (1967) 42–51 | DOI | MR | Zbl
[11] , On non-determinancy in simple computing devices. Acta Inform. 1 (1972) 336–344 | DOI | MR | Zbl
[12] , and , Complexity of multi-head finite automata: origins and directions. Theor. Comput. Sci. 412 (2011) 83–96 | DOI | MR | Zbl
[13] and , Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979) | MR
[14] , On the descriptional power of heads, counters, and pebbles. Theor. Comput. Sci. 330 (2005) 311–324 | DOI | MR | Zbl
[15] and , Reversible pushdown automata. J. Comput. System Sci. 78 (2012) 1814–1827 | DOI | MR | Zbl
[16] , , , and , Deterministic input-driven queue automata: finite turns, decidability, and closure properties. Theor. Comput. Sci. 578 (2015) 58–71 | DOI | MR | Zbl
[17] , and , Input-driven queue automata with internal transductions, in Language and Automata Theory and Applications (LATA 2016). Vol. 9618 of Lect. Notes Comput. Sci. Springer (2016) 156–167 | MR | Zbl
[18] , and , Reversible queue automata. Fund. Inform. 148 (2016) 341–368 | MR | Zbl
[19] , and , Queue automata: foundations and developments, in Reversibility and Universality. Vol. 30 of Emergence, Complexity and Computation. Springer (2018) 385–431 | MR | Zbl
[20] , A note on the P-completeness of deterministic one-way stack language. J. UCS 16 (2010) 795–799 | MR | Zbl
[21] , and , Church-Rosser Thue systems and formal languages. J. ACM 35 (1988) 324–344 | DOI | MR | Zbl
[22] , Two-way multihead automata over a one-letter alphabet. RAIRO: ITA 14 (1980) 67–82 | Numdam | MR | Zbl
[23] , Intercalation theorems for stack languages. In Symposium on Theory of Computing (STOC 1969). ACM Press (1969) 31–42 | Zbl
[24] , Über einen Automaten mit Pufferspeicherung. Computing 5 (1970) 57–70 | DOI | MR | Zbl
Cité par Sources :
