Document Open Access Logo

A Coalgebraic Take on Regular and omega-Regular Behaviour for Systems with Internal Moves

Author Tomasz Brengos

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2018.25.pdf
  • Filesize: 0.53 MB
  • 18 pages

Document Identifiers

Author Details

Tomasz Brengos
  • Faculty of Mathematics and Information Science, Warsaw University of Technology, ul. Koszykowa 75, 00-662 Warszawa, Poland

Cite As Get BibTex

Tomasz Brengos. A Coalgebraic Take on Regular and omega-Regular Behaviour for Systems with Internal Moves. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CONCUR.2018.25

Abstract

We present a general coalgebraic setting in which we define finite and infinite behaviour with Büchi acceptance condition for systems with internal moves. Since systems with internal moves are defined here as coalgebras for a monad, in the first part of the paper we present a construction of a monad suitable for modelling (in)finite behaviour. The second part of the paper focuses on presenting the concepts of a (coalgebraic) automaton and its (omega-) behaviour. We end the paper with coalgebraic Kleene-type theorems for (omega-) regular input. We discuss the setting in the context of non-deterministic (tree) automata and Segala automata.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • coalgebras
  • regular languages
  • omega regular languages
  • automata
  • Büchi automata
  • silent moves
  • internal moves
  • monads
  • saturation

Metrics

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

References

  1. Jirí Adámek, Mahdieh Haddadi, and Stefan Milius. Corecursive algebras, corecursive monads and bloom monads. Logical Methods in Computer Science, 10(3), 2014. URL: http://dx.doi.org/10.2168/LMCS-10(3:19)2014.
  2. Christel Baier and Marcus Grosser. Recognizing omega-regular languages with probabilistic automata. In Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, LICS '05, pages 137-146, Washington, DC, USA, 2005. IEEE Computer Society. URL: http://dx.doi.org/10.1109/LICS.2005.41.
  3. Christel Baier, Marcus Grösser, and Nathalie Bertrand. Probabilistic omega-automata. J. ACM, 59(1):1:1-1:52, 2012. URL: http://dx.doi.org/10.1145/2108242.2108243.
  4. Jon Beck. Distributive laws. In B. Eckmann, editor, Seminar on Triples and Categorical Homology Theory, pages 119-140, Berlin, Heidelberg, 1969. Springer Berlin Heidelberg. Google Scholar
  5. Stephen Bloom and Zoltán Ésik. Iteration Theories. The Equational Logic of Iterative Processes. Monographs in Theoretical Computer Science. Springer, 1993. Google Scholar
  6. Filippo Bonchi, Stefan Milius, Alexandra Silva, and Fabio Zanasi. Killing epsilons with a dagger: A coalgebraic study of systems with algebraic label structure. Theoretical Computer Science, 604:102-126, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.03.024.
  7. Tomasz Brengos. On coalgebras with internal moves. In Marcello M. Bonsangue, editor, Proc. CMCS, Lecture Notes in Computer Science, pages 75-97. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44124-4_5.
  8. Tomasz Brengos. Weak bisimulation for coalgebras over order enriched monads. Logical Methods in Computer Science, 11(2):1-44, 2015. URL: http://dx.doi.org/10.2168/LMCS-11(2:14)2015.
  9. Tomasz Brengos, Marino Miculan, and Marco Peressotti. Behavioural equivalences for coalgebras with unobservable moves. Journal of Logical and Algebraic Methods in Programming, 84(6):826-852, 2015. URL: http://dx.doi.org/10.1016/j.jlamp.2015.09.002.
  10. Tomasz Brengos and Marco Peressotti. A Uniform Framework for Timed Automata. In Josée Desharnais and Radha Jagadeesan, editors, 27th International Conference on Concurrency Theory (CONCUR 2016), volume 59 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1-26:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2016.26.
  11. Vincenzo Ciancia and Yde Venema. Stream automata are coalgebras. In Proc. CMCS, volume 7399 of Lecture Notes in Computer Science, pages 90-108, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32784-1_6.
  12. Corina Cîrstea. Generic infinite traces and path-based coalgebraic temporal logics. Electr. Notes Theor. Comput. Sci., 264(2):83-103, 2010. URL: http://dx.doi.org/10.1016/j.entcs.2010.07.015.
  13. Zoltán Ésik and Tamás Hajgató. Iteration grove theories with applications. In Proc. Algebraic Informatics, volume 5725 of Lecture Notes in Computer Science, pages 227-249. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03564-7_15.
  14. Zoltán Ésik and Werner Kuich. A Unifying Kleene Theorem for Weighted Finite Automata, pages 76-89. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. URL: http://dx.doi.org/10.1007/978-3-642-19391-0_6.
  15. Zoltán Ésik and Werner Kuich. Modern automata theory, 2013. URL: http://www.dmg.tuwien.ac.at/kuich/.
  16. Sergey Goncharov and Dirk Pattinson. Coalgebraic weak bisimulation from recursive equations over monads. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Proc. ICALP, volume 8573 of Lecture Notes in Computer Science, pages 196-207. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_17.
  17. Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata Logics, and Infinite Games: A Guide to Current Research, page 392. Springer-Verlag New York, Inc., New York, NY, USA, 2002. Google Scholar
  18. H. Peter Gumm. Elements of the general theory of coalgebras. LUATCS 99, Rand Afrikaans University, 1999. Google Scholar
  19. H. Peter Gumm. From t-coalgebras to filter structures and transition systems. In José Luiz Fiadeiro, Neil Harman, Markus Roggenbach, and Jan Rutten, editors, Algebra and Coalgebra in Computer Science, pages 194-212, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. URL: http://dx.doi.org/doi.org/10.1007/11548133_13.
  20. Ichiro Hasuo. Generic forward and backward simulations. In Prof. CONCUR, volume 4137 of Lecture Notes in Computer Science, pages 406-420, 2006. URL: http://dx.doi.org/10.1007/11817949_27.
  21. Ichiro Hasuo, Bart Jacobs, and Ana Sokolova. Generic trace semantics via coinduction. Logical Methods in Computer Science, 3(4), 2007. URL: http://dx.doi.org/10.2168/LMCS-3(4:11)2007.
  22. John E. Hopcroft, Rajeev Motwani, Rotwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computability. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2nd edition, 2000. Google Scholar
  23. Martin Hyland and John Power. The category theoretic understanding of universal algebra: Lawvere theories and monads. Electronic Notes in Theoretical Computer Science, 172:437-458, 2007. URL: http://dx.doi.org/10.1016/j.entcs.2007.02.019.
  24. Bart Jacobs. Trace semantics for coalgebras. Electr. Notes Theor. Comput. Sci., 106:167-184, 2004. URL: http://dx.doi.org//doi.org/10.1016/j.entcs.2004.02.031.
  25. Bart Jacobs. Coalgebraic trace semantics for combined possibilistic and probabilistic systems. In Proc. CMCS, Electronic Notes in Theoretical Computer Science, pages 131-152, 2008. URL: http://dx.doi.org/10.1016/j.entcs.2008.05.023.
  26. Bart Jacobs, Alexandra Silva, and Ana Sokolova. Trace semantics via determinization. In Proc. CMCS, volume 7399 of Lecture Notes in Computer Science, pages 109-129, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32784-1_7.
  27. F. W. Lawvere. Functorial semantics of algebraic theories. Proc. Nat. Acad. Sci. U.S.A., 50:869-872, 1963. URL: http://dx.doi.org/10.1073/pnas.50.5.869.
  28. Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer-Verlang New York, 1978. URL: http://dx.doi.org/10.1007/978-1-4757-4721-8.
  29. Robin Milner. Communication and Concurrency. Prentice-Hall, 1989. Google Scholar
  30. David Park. Concurrency and automata on infinite sequences. In Peter Deussen, editor, Theoretical Computer Science, pages 167-183, Berlin, Heidelberg, 1981. Springer Berlin Heidelberg. Google Scholar
  31. Jean-Eric Pin and Dominique Perrin. Infinite Words: Automata, Semigroups, Logic and Games, page 538. Elsevier, 2004. Google Scholar
  32. Jan J. M. M. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, 249(1):3-80, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(00)00056-6.
  33. Roberto Segala. Modeling and Verification of Randomized Distributed Real-Time Systems. PhD thesis, Massachusetts Institute of Technology, 1995. Google Scholar
  34. Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic processes. In Proc. CONCUR, volume 836 of Lecture Notes in Computer Science, pages 481-496, 1994. URL: http://dx.doi.org/10.1007/978-3-540-48654-1_35.
  35. Alexandra Silva and Bram Westerbaan. A coalgebraic view of ε-transitions. In Reiko Heckel and Stefan Milius, editors, Proc. CALCO, volume 8089 of Lecture Notes in Computer Science, pages 267-281. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40206-7_20.
  36. Natsuki Urabe, Shunsuke Shimizu, and Ichiro Hasuo. Coalgebraic Trace Semantics for Buechi and Parity Automata. In Josée Desharnais and Radha Jagadeesan, editors, 27th International Conference on Concurrency Theory (CONCUR 2016), 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.
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