Geodesic
Diving into the queue
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 89-110

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
DOI : 10.1051/ita/2018009
Classification : 68Q45, 68Q15
Keywords: Queue automata, logspace Turing machines, formal languages, decidability questions

Beier, Simon 1 ; Kutrib, Martin 1 ; Malcher, Andreas 1 ; Wendlandt, Matthias 1

1 
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :