Document Open Access Logo

Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid

Author Chris Köcher

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.45.pdf
  • Filesize: 485 kB
  • 14 pages

Document Identifiers

Author Details

Chris Köcher

Cite As Get BibTex

Chris Köcher. Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.45

Abstract

Partially lossy queue monoids (or plq monoids) model the behavior of queues that can forget arbitrary parts of their content. While many decision problems on recognizable subsets in the plq monoid are decidable, most of them are undecidable if the sets are rational. In particular, in this monoid the classes of rational and recognizable subsets do not coincide. By restricting multiplication and iteration in the construction of rational sets and by allowing complementation we obtain precisely the class of recognizable sets. From these special rational expressions we can obtain an MSO logic describing the recognizable subsets. Moreover, we provide similar results for the class of aperiodic subsets in the plq monoid.

Subject Classification

Keywords
  • Partially Lossy Queues
  • Transformation Monoid
  • Rational Sets
  • Recognizable Sets
  • Aperiodic Sets
  • MSO logic

Metrics

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

References

  1. Parosh Aziz Abdulla and Bengt Jonsson. Verifying programs with unreliable channels. Inf. Comput., 127(2):91-101, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0053.
  2. Jean Berstel. Transductions and Context-Free Languages. Teubner Studienbücher, 1979. URL: http://dx.doi.org/10.1007/978-3-663-09367-1.
  3. Daniel Brand and Pitro Zafiropulo. On communicating finite-state machines. J. ACM, 30(2):323-342, 1983. URL: http://dx.doi.org/10.1145/322374.322380.
  4. J. Richard Büchi. Weak second-order arithmetic and finite automata. Mathematical Logic Quarterly, 6(1-6):66-92, 1960. URL: http://dx.doi.org/10.1002/malq.19600060105.
  5. Gérard Cécé, Alain Finkel, and S. Purushothaman Iyer. Unreliable channels are easier to verify than perfect channels. Inf. Comput., 124(1):20-31, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0003.
  6. Marek Chrobak and Wojciech Rytter. Unique deciperability for partially commutative alphabet (extended abstract). In Jozef Gruska, Branislav Rovan, and Juraj Wiedermann, editors, Mathematical Foundations of Computer Science 1986, Bratislava, Czechoslovakia, August 25-29, 1996, Proceedings, volume 233 of Lecture Notes in Computer Science, pages 256-263. Springer, 1986. URL: http://dx.doi.org/10.1007/BFb0016249.
  7. Volker Diekert and Grzegorz Rozenberg. The book of traces. World scientific, 1995. URL: http://dx.doi.org/10.1142/9789814261456.
  8. Alain Finkel. Decidability of the termination problem for completely specified protocols. Distributed Computing, 7(3):129-135, 1994. URL: http://dx.doi.org/10.1007/BF02277857.
  9. Alan Gibbons and Wojciech Rytter. On the decidability of some problems about rational subsets of free partially commutative monoids. Theor. Comput. Sci., 48(3):329-337, 1986. URL: http://dx.doi.org/10.1016/0304-3975(86)90101-5.
  10. Giovanna Guaiana, Antonio Restivo, and Sergio Salemi. On aperiodic trace languages. In Christian Choffrut and Matthias Jantzen, editors, STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings, volume 480 of Lecture Notes in Computer Science, pages 76-88. Springer, 1991. URL: http://dx.doi.org/10.1007/BFb0020789.
  11. 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.
  12. Mark Kambites. Formal languages and groups as memory. Communications in Algebra, 37(1):193-208, 2009. URL: http://dx.doi.org/10.1080/00927870802243580.
  13. Stephen C. Kleene. Representation of events in nerve nets and finite automata. Automata Studies, 1956. Google Scholar
  14. Chris Köcher. Einbettungen in das Transformationsmonoid einer vergesslichen Warteschlange. Master’s thesis, TU Ilmenau, 2016. URL: http://dx.doi.org/10.13140/RG.2.2.21984.99842.
  15. Chris Köcher, Dietrich Kuske, and Olena Prianychnykova. The transformation monoid of a partially lossy queue. RAIRO - Theoretical Informatics and Applications, 2018. To appear. Google Scholar
  16. Markus Lohrey. The rational subset membership problem for groups: a survey. In Groups St Andrews, volume 422, pages 368-389. Cambridge University Press, 2013. URL: http://dx.doi.org/10.1017/CBO9781316227343.024.
  17. Benoît Masson and Philippe Schnoebelen. On verifying fair lossy channel systems. In Krzysztof Diks and Wojciech Rytter, editors, Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings, 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.
  18. J. D. McKnight. Kleene quotient theorems. Pacific Journal of Mathematics, 14(4):1343-1352, 1964. Google Scholar
  19. Robert McNaughton and Seymour A. Papert. Counter-Free Automata, volume 65. The MIT Press, 1971. Google Scholar
  20. Anca Muscholl and Holger Petersen. A note on the commutative closure of star-free languages. Inf. Process. Lett., 57(2):71-74, 1996. URL: http://dx.doi.org/10.1016/0020-0190(95)00187-5.
  21. Edward Ochmański. Regular behaviour of concurrent systems. Bulletin of the EATCS, 27:56-67, 1985. Google Scholar
  22. Jean-Éric Pin. Mathematical foundations of automata theory. Lecture notes LIAFA, Université Paris, 7, 2010. Google Scholar
  23. Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4):264-268, 1946. Google Scholar
  24. Elaine Render and Mark Kambites. Rational subsets of polycyclic monoids and valence automata. Inf. Comput., 207(11):1329-1339, 2009. URL: http://dx.doi.org/10.1016/j.ic.2009.02.012.
  25. Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965. URL: http://dx.doi.org/10.1016/S0019-9958(65)90108-7.
  26. Wolfgang Thomas. Languages, automata, and logic. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages: Volume 3 Beyond Words, 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