2026-08-17T10:34:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9908 2024-03-06T10:45:05Z ddc:004 open_access

The Cayley-Graph of the Queue Monoid: Logic and Decidability Abu Zaid, Faried Köcher, Chris Queues Transformation Monoid Cayley-Graph Logic First-Order Theory MSO Theory Model Checking 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Faried Abu Zaid and Chris Köcher 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.9 urn:nbn:de:0030-drops-99088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.9 eng https://creativecommons.org/licenses/by/3.0/legalcode