Issue |
RAIRO-Theor. Inf. Appl.
Volume 52, Number 2-3-4, April–December 2018
8th Workshop on Non-classical Models of Automata and Applications (NCMA 2016)
|
|
---|---|---|
Page(s) | 89 - 110 | |
DOI | https://doi.org/10.1051/ita/2018009 | |
Published online | 18 January 2019 |
Regular Article
Diving into the queue
Institut für Informatik,
Universität Giessen, Arndtstr. 2,
35392 Giessen, Germany.
* Corresponding author: andreas.malcher@informatik.uni-giessen.de
Received:
21
November
2018
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.
Mathematics Subject Classification: 68Q45 / 68Q15
Key words: Queue automata / logspace Turing machines / formal languages / decidability questions
© EDP Sciences, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.