The Cayley-graph of the queue monoid: logic and decidability

Abu Zaid, Faried GND; Köcher, Chris GND

We investigate the decidability of logical aspects of graphs that arise as Cayley-graphs of the so-called queue monoids. These monoids model the behavior of the classical (reliable) fifo-queues. We answer a question raised by Huschenbett, Kuske, and Zetzsche and prove the decidability of the first-order theory of these graphs with the help of an - at least for the authors - new combination of the well-known method from Ferrante and Rackoff and an automata-based approach. On the other hand, we prove that the monadic second-order of the queue monoid's Cayley-graph is undecidable.

Cite

Citation style:
The Cayley-graph of the queue monoid: logic and decidability, 2018. . 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. https://doi.org/10.4230/LIPIcs.FSTTCS.2018.9
Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:

Export