Document Open Access Logo

The Cayley-Graph of the Queue Monoid: Logic and Decidability

Authors Faried Abu Zaid, Chris Köcher

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.9.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Faried Abu Zaid
  • Camelot Management Consultants, CoE Artificial Intelligence for Information Management, Munich, Germany
Chris Köcher
  • Technische Universität Ilmenau, Automata and Logics Group, Ilmenau, Germany

Funding

  • Abu Zaid, Faried: The presented work was conducted while the first author was affiliated with the Technische Universität Ilmenau.

Cite As Get BibTex

Faried Abu Zaid and Chris Köcher. The Cayley-Graph of the Queue Monoid: Logic and Decidability. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2018.9

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic
  • Theory of computation → Models of computation
  • Information systems → Data structures
Keywords
  • Queues
  • Transformation Monoid
  • Cayley-Graph
  • Logic
  • First-Order Theory
  • MSO Theory
  • Model Checking

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Parosh A. Abdulla and Bengt Jonsson. Verifying Programs with Unreliable Channels. Information and Computation, 127(2):91-101, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0053.
  2. Benedikt Bollig. Formal Models of Communicating Systems: Languages, Automata, and Monadic Second-Order Logic. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-32923-4.
  3. Daniel Brand and Pitro Zafiropulo. On Communicating Finite-State Machines. Journal of the ACM, 30(2), 1983. URL: http://dx.doi.org/10.1145/322374.322380.
  4. James W Cannon, David BA Epstein, Derek F Holt, Silvio VF Levy, Michael S Paterson, and William P Thurston. Word Processing in Groups. Jones and Barlett Publ., Boston, MA, 1992. Google Scholar
  5. Gérard Cécé, Alain Finkel, and S. Purushotaman Iyer. Unreliable Channels Are Easier to Verify than Perfect Channels. Information and Computation, 124(1):20-31, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0003.
  6. Christian Delhommé, Teodor Knapik, and D. Gnanaraj Thomas. Using TransitiveendashClosure Logic for Deciding Linear Properties of Monoids. In Mathematical Foundations of Computer Science 2003, volume 2747 of Lecture Notes in Computer Science, pages 378-387. Springer, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45138-9_32.
  7. Andrzej Ehrenfeucht. An Application of Games to the Completeness Problem for Formalized Theories. Fundamenta Mathematicae, 49(129-141):13, 1961. Google Scholar
  8. Jeanne Ferrante and Charles W. Rackoff. The Computational Complexity of Logical Theories. Number 718 in Lecture Notes in Mathematics. Springer, 1979. URL: http://dx.doi.org/10.1007/BFb0062837.
  9. Roland Fraïssé. Sur Quelques Classifications Des Systèmes de Relations. Université d'Alger, Publications Scientifiques, Série A, 1:35-182, 1954. Google Scholar
  10. Erich Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, Texts in Theoretical Computer Science an EATCS Series, pages 125-230. Springer, 2007. URL: http://dx.doi.org/10.1007/3-540-68804-8_3.
  11. James A. Green. On the Structure of Semigroups. Annals of Mathematics, pages 163-172, 1951. Google Scholar
  12. Christoph Haase, Sylvain Schmitz, and Philippe Schnoebelen. The Power of Priority Channel Systems. Logical Methods in Computer Science, 10(4:4), 2014. URL: http://dx.doi.org/10.2168/LMCS-10(4:4)2014.
  13. Martin Huschenbett, Dietrich Kuske, and Georg Zetzsche. The Monoid of Queue Actions. Semigroup forum, 95(3):475-508, 2017. URL: http://dx.doi.org/10.1007/s00233-016-9835-4.
  14. Mark Kambites. Formal Languages and Groups as Memory. Communications in Algebra, 37(1):193-208, 2009. URL: http://dx.doi.org/10.1080/00927870802243580.
  15. Olga Kharlampovich, Bakhadyr Khoussainov, and Alexei Miasnikov. From Automatic Structures to Automatic Groups. Groups, Geometry, and Dynamics, 8(1):157-198, 2014. URL: http://dx.doi.org/10.4171/GGD/221.
  16. Bakhadyr Khoussainov and Anil Nerode. Automatic Presentations of Structures. In Logic and Computational Complexity, volume 960 of Lecture Notes in Computer Science, pages 367-392. Springer, 1995. URL: http://dx.doi.org/10.1007/3-540-60178-3_93.
  17. Chris Köcher. Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid. In STACS'18, volume 96 of LIPIcs, pages 45:1-45:14. Dagstuhl Publishing, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2018.45.
  18. Chris Köcher, Dietrich Kuske, and Olena Prianychnykova. The Inclusion Structure of Partially Lossy Queue Monoids and Their Trace Submonoids. RAIRO - Theoretical Informatics and Applications, 52(1):55-86, 2018. URL: http://dx.doi.org/10.1051/ita/2018003.
  19. Dietrich Kuske and Markus Lohrey. Logical Aspects of Cayley-Graphs: The Group Case. Annals of Pure and Applied Logic, 131(1):263-286, 2005. URL: http://dx.doi.org/10.1016/j.apal.2004.06.002.
  20. Dietrich Kuske and Markus Lohrey. Logical Aspects of Cayley-Graphs: The Monoid Case. International Journal of Algebra and Computation, 16(02):307-340, 2006. URL: http://dx.doi.org/10.1142/S0218196706003001.
  21. Dietrich Kuske and Markus Lohrey. Automatic Structures of Bounded Degree Revisited. The Journal of Symbolic Logic, 76(4):1352-1380, 2011. URL: http://dx.doi.org/10.2178/jsl/1318338854.
  22. Benoît Masson and Philippe Schnoebelen. On Verifying Fair Lossy Channel Systems. In MFCS'02, volume 2420 of Lecture Notes in Computer Science, pages 543-555. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45687-2_45.
  23. David E. Muller and Paul E. Schupp. The Theory of Ends, Pushdown Automata, and Second-Order Logic. Theoretical Computer Science, 37:51-75, January 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90087-8.
  24. Paliath Narendran and Friedrich Otto. Some Results on Equational Unification. In 10th International Conference on Automated Deduction, volume 449 of Lecture Notes in Computer Science, pages 276-291. Springer, 1990. URL: http://dx.doi.org/10.1007/3-540-52885-7_94.
  25. Jean-Éric Pin. Mathematical Foundations of Automata Theory. Lecture notes LIAFA, Université Paris, 7, 2010. Google Scholar
  26. Neil Robertson and Paul D. Seymour. Graph Minors, Part III: Planar Tree-Width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. URL: http://dx.doi.org/10.1016/0095-8956(84)90013-3.
  27. Jacques Sakarovitch. Kleene’s Theorem Revisited. In Trends, Techniques, and Problems in Theoretical Computer Science, volume 281 of Lecture Notes in Computer Science, pages 39-50. Springer, 1986. URL: http://dx.doi.org/10.1007/3540185356_29.
  28. D. Seese. The Structure of the Models of Decidable Monadic Theories of Graphs. Annals of Pure and Applied Logic, 53(2):169-195, 1991. URL: http://dx.doi.org/10.1016/0168-0072(91)90054-P.
  29. Wolfgang Thomas. Languages, Automata, and Logic. In Grzegorz Rozenberg and Arto Salomaa, editors, Beyond Words, volume 3 of Handbook of Formal Languages, pages 389-455. Springer, 1997. URL: http://dx.doi.org/10.1007/978-3-642-59126-6_7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact