Document Open Access Logo

Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages

Authors Vincenzo Ciancia, Yde Venema

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2019.5.pdf
  • Filesize: 0.5 MB
  • 18 pages

Document Identifiers

Author Details

Vincenzo Ciancia
  • Istituto di Scienza e Tecnologie dell'Informazione "A. Faedo" - Consiglio Nazionale delle Ricerche, Pisa, Italy
Yde Venema
  • Institute for Logic, Language and Computation, Universiteit van Amsterdam, Amsterdam, The Netherlands

Acknowledgements

The authors wish to thank Oded Maler and Ludwig Staiger for useful discussions about right congruences and characterisations of omega-regularity.

Cite AsGet BibTex

Vincenzo Ciancia and Yde Venema. Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CALCO.2019.5

Abstract

In this work, we provide a simple coalgebraic characterisation of regular omega-languages based on languages of lassos, and prove a number of related mathematical results, framed into the theory of a new kind of automata called Omega-automata. In earlier work we introduced Omega-automata as two-sorted structures that naturally operate on lassos, pairs of words encoding ultimately periodic streams (infinite words). Here we extend the scope of these Omega-automata by proposing them as a new kind of acceptor for arbitrary streams. We prove that Omega-automata are expressively complete for the regular omega-languages. We show that, due to their coalgebraic nature, Omega-automata share some attractive properties with deterministic automata operating on finite words, properties that other types of stream automata lack. In particular, we provide a simple, coalgebraic definition of bisimilarity between Omega-automata that exactly captures language equivalence and allows for a simple minimization procedure. We also prove a coalgebraic Myhill-Nerode style theorem for lasso languages, and use this result, in combination with a closure property on stream languages called lasso determinacy, to give a characterization of regular omega-languages.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Automata over infinite objects
Keywords
  • omega-automata
  • regular omega-languages
  • coalgebra
  • streams
  • bisimilarity

Metrics

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

References

  1. Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87-106, Elsevier, 1987. URL: http://dx.doi.org/10.1016/0890-5401(87)90052-6.
  2. Dana Angluin, Udi Boker, and Dana Fisman. Families of dfas as acceptors of ω-regular languages. Logical Methods in Computer Science, Volume 14, Issue 1, February 2018. URL: http://dx.doi.org/10.23638/LMCS-14(1:15)2018.
  3. Dana Angluin and Dana Fisman. Learning regular omega languages. In Algorithmic Learning Theory, volume 8776 of Lecture Notes in Computer Science, pages 125-139. Springer International Publishing, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11662-4_10.
  4. André Arnold. A syntactic congruence for rational ω-languages. Theoretical Computer Science, 39:333-335, Elsevier, 1985. URL: http://dx.doi.org/10.1016/0304-3975(85)90148-3.
  5. Simone Barlocco, Clemens Kupke, and Jurriaan Rot. Coalgebra learning via duality. In Foundations of Software Science and Computation Structures, volume 11425 of Lecture Notes in Computer Science, pages 62-79. Springer International Publishing, 2019. URL: http://dx.doi.org/10.1007/978-3-030-17127-8_4.
  6. Tomasz Brengos. A coalgebraic take on regular and omega-regular behaviour for systems with internal moves. In International Conference on Concurrency Theory, volume 118 of LIPIcs, pages 25:1-25:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2018.25.
  7. Hugues Calbrix, Maurice Nivat, and Andreas Podelski. Ultimately periodic words of rational ω-languages. In Mathematical Foundations of Programming Semantics, volume 802 of Lecture Notes in Computer Science, pages 554-566. Springer, 1993. URL: http://dx.doi.org/10.1007/3-540-58027-1_27.
  8. Vincenzo Ciancia and Matteo Sammartino. A class of automata for the verification of infinite, resource-allocating behaviours. In Trustworthy Global Computing, volume 8902 of Lecture Notes in Computer Science, pages 97-111. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45917-1_7.
  9. Vincenzo Ciancia and Yde Venema. Stream automata are coalgebras. In Coalgebraic Methods in Computer Science, volume 7399 of Lecture Notes in Computer Science, pages 90-108. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32784-1_6.
  10. Szilárd Fazekas. Powers of regular languages. In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory, volume 5583 of Lecture Notes in Computer Science, pages 221-227. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02737-6_17.
  11. E. Grädel, W. Thomas, and T. Wilke, editors. Automata, Logic, and Infinite Games, volume 2500 of Lecture Notes in Computer Science. Springer, 2002. Google Scholar
  12. Yong Li, Yu-Fang Chen, Lijun Zhang, and Depeng Liu. A novel learning algorithm for büchi automata based on family of dfas and classification trees. In Tools and Algorithms for the Construction and Analysis of Systems, Part I, volume 10205 of Lecture Notes in Computer Science, pages 208-226, 2017. URL: http://dx.doi.org/10.1007/978-3-662-54577-5_12.
  13. Christof Löding. Efficient minimization of deterministic weak ω-automata. Information Processing Letters, 79:105-109, Elsevier, 2001. URL: http://dx.doi.org/10.1016/S0020-0190(00)00183-6.
  14. Oded Maler and Ludwig Staiger. On syntactic congruences for ω-languages. Theoretical Computer Science, 183:93-112, Elsevier, 1997. URL: http://dx.doi.org/10.1007/3-540-56503-5_58.
  15. Dominique Perrin and Jean-Éric Pin. Infinite Words: Automata, Semigroups, Logic and Games. Elsevier, 2004. Google Scholar
  16. J. Rutten. Automata and coinduction (an exercise in coalgebra). In International Conference on Concurrency Theory, Lecture Notes in Computer Science, pages 194-218. Springer, 1998. URL: http://dx.doi.org/10.1007/BFb0055624.
  17. J. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, 249:3-80, Elsevier, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(00)00056-6.
  18. Ludwig Staiger. Finite-state ω-languages. Journal of Computer and System Sciences, 27:434-448, Elsevier, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90051-X.
  19. Natsuki Urabe and Ichiro Hasuo. Categorical büchi and parity conditions via alternating fixed points of functors. In Coalgebraic Methods in Computer Science, Revised Selected Papers, volume 11202 of Lecture Notes in Computer Science, pages 214-234. Springer, 2018. URL: http://dx.doi.org/10.1007/978-3-030-00389-0_12.
  20. Natsuki Urabe, Shunsuke Shimizu, and Ichiro Hasuo. Coalgebraic trace semantics for buechi and parity automata. In International Conference on Concurrency Theory, volume 59 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2016.24.
  21. Thomas Wilke. An algebraic theory for regular languages of finite and infinite words. International Journal of Algebra and Computation, 03(04):447-489, 1993. URL: http://dx.doi.org/10.1142/S0218196793000287.
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 Imprint Privacy Contact