Cited By
View all- Colcombet TPetrişan D(2017)Automata and minimizationACM SIGLOG News10.1145/3090064.30900664:2(4-27)Online publication date: 3-May-2017
A short introduction to the coalgebraic method
Abstract
This article contains a brief introduction to coalgebra and an overview of a recent proof of correctness for Brzozowski's algorithm which uses coalgebraic techniques. In the discussion section we briefly discuss the most active research lines in the coalgebra community and take a personal outlook at what future might bring for the field.
References
[1]
Andreas Abel, Brigitte Pientka, David Thibodeau, and Anton Setzer. 2013. Copatterns: Programming Infinite Structures by Observations. In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '13). ACM, New York, NY, USA, 27--38.
[2]
Jirí Adámek, Stefan Milius, Robert S. R. Myers, and Henning Urbat. 2014a. Generalized Eilenberg Theorem I: Local Varieties of Languages. In Foundations of Software Science and Computation Structures - 17th International Conference, FOSSACS 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Grenoble, France, April 5--13, 2014, Proceedings (Lecture Notes in Computer Science), Anca Muscholl (Ed.), Vol. 8412. Springer, 366--380.
[3]
Jirí Adámek, Robert S. R. Myers, Henning Urbat, and Stefan Milius. 2014b. On Continuous Nondeterminism and State Minimality. Electr. Notes Theor. Comput. Sci. 308 (2014), 3--23.
[4]
Carolyn Jane Anderson, Nate Foster, Arjun Guha, Jean-Baptiste Jeannin, Dexter Kozen, Cole Schlesinger, and David Walker. 2014. NetkAT: semantic foundations for networks. In The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '14, San Diego, CA, USA, January 20--21, 2014, Suresh Jagannathan and Peter Sewell (Eds.). ACM, 113--126.
[5]
Dana Angluin. 1987. Learning Regular Sets from Queries and Counterexamples. Inf. Comput. 75, 2 (1987), 87--106.
[6]
Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, and Radu Mardare. 2013. On-the-Fly Exact Computation of Bisimilarity Distances. In Tools and Algorithms for the Construction and Analysis of Systems - 19th International Conference, TACAS 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16--24, 2013. Proceedings (Lecture Notes in Computer Science), Nir Piterman and Scott A. Smolka (Eds.), Vol. 7795. Springer, 1--15.
[7]
Paolo Baldan and Daniele Gorla (Eds.). 2014. CONCUR 2014 - Concurrency Theory - 25th International Conference, CONCUR 2014, Rome, Italy, September 2--5, 2014. Proceedings. Lecture Notes in Computer Science, Vol. 8704. Springer.
[8]
Jon Barwise and Larry Moss. 1996. Vicious Circles. Center for the Study of Language and Information - Stanford.
[9]
Nick Bezhanishvili, Clemens Kupke, and Prakash Panangaden. 2012. Minimization via Duality. In Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3--6, 2012. Proceedings (Lecture Notes in Computer Science), C.-H. Luke Ong and Ruy J. G. B. de Queiroz (Eds.), Vol. 7456. Springer, 191--205.
[10]
Filippo Bonchi, Marcello M. Bonsangue, Georgiana Caltais, Jan J. M. M. Rutten, and Alexandra Silva. 2012. Final Semantics for Decorated Traces. Electr. Notes Theor. Comput. Sci. 286 (2012), 73--86.
[11]
Filippo Bonchi, Marcello M. Bonsangue, Helle Hvid Hansen, Prakash Panangaden, Jan J. M. M. Rutten, and Alexandra Silva. 2014. Algebra-coalgebra duality in Brzozowski's minimization algorithm. ACM Trans. Comput. Log. 15, 1 (2014), 3.
[12]
Filippo Bonchi, Marcello M. Bonsangue, Jan J. M. M. Rutten, and Alexandra Silva. 2012. Brzozowski's Algorithm (Co)Algebraically. In Logic and Program Semantics - Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday (Lecture Notes in Computer Science), Robert L. Constable and Alexandra Silva (Eds.), Vol. 7230. Springer, 12--23.
[13]
Filippo Bonchi, Georgiana Caltais, Damien Pous, and Alexandra Silva. 2013. Brzozowski's and Up-To Algorithms for Must Testing. In Programming Languages and Systems - 11th Asian Symposium, APLAS 2013, Melbourne, VIC, Australia, December 9--11, 2013. Proceedings (Lecture Notes in Computer Science), Chung-chieh Shan (Ed.), Vol. 8301. Springer, 1--16.
[14]
Filippo Bonchi and Damien Pous. 2013. Checking NFA equivalence with bisimulations up to congruence, See Giacobazzi and Cousot {2013}, 457--468.
[15]
Filippo Bonchi and Damien Pous. 2015. Hacking nondeterminism with induction and coinduction. Commun. ACM 58, 2 (2015), 87--95.
[16]
Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. 2015. Full Abstraction for Signal Flow Graphs, See Rajamani and Walker {2015}, 515--526.
[17]
Marcello M. Bonsangue, Stefan Milius, and Alexandra Silva. 2013. Sound and Complete Axiomatizations of Coalgebraic Language Equivalence. ACM Trans. Comput. Log. 14, 1 (2013), 7.
[18]
Michele Boreale. 2009. Weighted Bisimulation in Linear Algebraic Form. In CONCUR 2009 - Concurrency Theory, 20th International Conference, CONCUR 2009, Bologna, Italy, September 1--4, 2009. Proceedings (Lecture Notes in Computer Science), Mario Bravetti and Gianluigi Zavattaro (Eds.), Vol. 5710. Springer, 163--177.
[19]
Pavol Cerný, Thomas A. Henzinger, and Arjun Radhakrishna. 2010. Simulation Distances, See Gastin and Laroussinie {2010}, 253--268.
[20]
Corina Cîrstea, Alexander Kurz, Dirk Pattinson, Lutz Schröder, and Yde Venema. 2011. Modal Logics are Coalgebraic. Comput. J. 54, 1 (2011), 31--41.
[21]
Josee Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. 1999. Metrics for Labeled Markov Systems. In CONCUR '99: Concurrency Theory, 10th International Conference, Eindhoven, The Netherlands, August 24--27, 1999, Proceedings (Lecture Notes in Computer Science), Jos C. M. Baeten and Sjouke Mauw (Eds.), Vol. 1664. Springer, 258--273.
[22]
Monica Dinculescu, Christopher Hundt, Prakash Panangaden, Joelle Pineau, and Doina Precup. 2011. The Duality of State and Observation in Probabilistic Transition Systems. In Logic, Language, and Computation - 9th International Tbilisi Symposium on Logic, Language, and Computation, TbiLLC 2011, Kutaisi, Georgia, September 26--30, 2011, Revised Selected Papers (Lecture Notes in Computer Science), Guram Bezhanishvili, Sebastian Löbner, Vincenzo Marra, and Frank Richter (Eds.), Vol. 7758. Springer, 206--230.
[23]
Nate Foster, Dexter Kozen, Matthew Milano, Alexandra Silva, and Laure Thompson. 2015. A Coalgebraic Decision Procedure for NetKAT, See Rajamani and Walker {2015}, 343--355.
[24]
Paul Gastin and François Laroussinie (Eds.). 2010. CONCUR 2010 - Concurrency Theory, 21th International Conference, CONCUR 2010, Paris, France, August 31-September 3, 2010. Proceedings. Lecture Notes in Computer Science, Vol. 6269. Springer.
[25]
Roberto Giacobazzi and Radhia Cousot (Eds.). 2013. The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '13, Rome, Italy - January 23--25, 2013. ACM. http: //dl.acm.org/citation.cfm?id=2429069
[26]
Sergey Goncharov, Stefan Milius, and Alexandra Silva. 2014. Towards a Coalgebraic Chomsky Hierarchy - (Extended Abstract). In Theoretical Computer Science - 8th IFIP TC 1/WG 2.2 International Conference, TCS 2014, Rome, Italy, September 1--3, 2014. Proceedings (Lecture Notes in Computer Science), Josep Diaz, Ivan Lanese, and Davide Sangiorgi (Eds.), Vol. 8705. Springer, 265--280.
[27]
Rajeev Goré, Clemens Kupke, Dirk Pattinson, and Lutz Schröder. 2010. Global Caching for Coalgebraic Description Logics. In Automated Reasoning, 5th International Joint Conference, IJCAR 2010, Edinburgh, UK, July 16--19, 2010. Proceedings (Lecture Notes in Computer Science), Jürgen Giesl and Reiner Hähnle (Eds.), Vol. 6173. Springer, 46--60.
[28]
Ichiro Hasuo. 2010. Generic Forward and Backward Simulations II: Probabilistic Simulation, See Gastin and Laroussinie {2010}, 447--461.
[29]
Bart Jacobs, Milad Niqui, Jan J. M. M. Rutten, and Alexandra Silva. 2011. Preface. Theor. Comput. Sci. 412, 38 (2011), 4967--4968.
[30]
Bart Jacobs, JJMM Rutten, and others. 1997. An introduction to (co) algebra and (co) induction. EATCS Bulletin 62 (1997), 222--259.
[31]
Bart Jacobs and Alexandra Silva. 2014. Automata Learning: A Categorical Perspective. In Horizons of the Mind. A Tribute to Prakash Panangaden - Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday (Lecture Notes in Computer Science), Franck van Breugel, Elham Kashefi, Catuscia Palamidessi, and Jan Rutten (Eds.), Vol. 8464. Springer, 384--406.
[32]
Jean-Baptiste Jeannin, Dexter Kozen, and Alexandra Silva. 2013. Language Constructs for Non-Well-Founded Computation. In Programming Languages and Systems - 22nd European Symposium on Programming, ESOP 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16--24, 2013. Proceedings (Lecture Notes in Computer Science), Matthias Felleisen and Philippa Gardner (Eds.), Vol. 7792. Springer, 61--80.
[33]
Henning Kerstan and Barbara König. 2012. Coalgebraic Trace Semantics for Probabilistic Transition Systems Based on Measure Theory. In CONCUR 2012 - Concurrency Theory - 23rd International Conference, CONCUR 2012, Newcastle upon Tyne, UK, September 4--7, 2012. Proceedings (Lecture Notes in Computer Science), Maciej Koutny and Irek Ulidowski (Eds.), Vol. 7454. Springer, 410--424.
[34]
Stefan Kiefer and Björn Wachter. 2014. Stability and Complexity of Minimising Probabilistic Automata. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8--11, 2014, Proceedings, Part II (Lecture Notes in Computer Science), Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias (Eds.), Vol. 8573. Springer, 268--279.
[35]
Dexter Kozen. 1997. Kleene Algebra with Tests. ACM Trans. Program. Lang. Syst. 19, 3 (1997), 427--443.
[36]
Agnieszka Kulacka, Dirk Pattinson, and Lutz Schröder. 2013. Syntactic Labelled Tableaux for Lukasiewicz Fuzzy ALC. In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3--9, 2013, Francesca Rossi (Ed.). IJCAI/AAAI. http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6831
[37]
Jean-Marie Madiot, Damien Pous, and Davide Sangiorgi. 2014. Bisimulations Upto: Beyond First-Order Transition Systems, See Baldan and Gorla {2014}, 93--108.
[38]
Michael W. Mislove, Joël Ouaknine, Dusko Pavlovic, and James Worrell. 2004. Duality for Labelled Markov Processes. In Foundations of Software Science and Computation Structures, 7th International Conference, FOSSACS 2004, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004, Barcelona, Spain, March 29 -- April 2, 2004, Proceedings (Lecture Notes in Computer Science), Igor Walukiewicz (Ed.), Vol. 2987. Springer, 393--407.
[39]
Damien Pous. 2008. Techniques modulo pour les bisimulations. Ph.D. Dissertation. PhD thesis, ENS Lyon.
[40]
Sriram K. Rajamani and David Walker (Eds.). 2015. Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, January 15--17, 2015. ACM. http://dl.acm.org/citation.cfm?id=2676726
[41]
Jurriaan Rot, Filippo Bonchi, Marcello Bonsangue, Damien Pous, JJMM Rutten, and Alexandra Silva. 2014. Enhanced coalgebraic bisimulation. Mathematical Structures in Computer Science (to appear, 2014) (2014).
[42]
Jurriaan Rot, Marcello M. Bonsangue, and Jan J. M. M. Rutten. 2013. Coalgebraic Bisimulation-Up-To. In SOFSEM 2013: Theory and Practice of Computer Science, 39th International Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 26--31, 2013. Proceedings (Lecture Notes in Computer Science), Peter van Emde Boas, Frans C. A. Groen, Giuseppe F. Italiano, Jerzy R. Nawrocki, and Harald Sack (Eds.), Vol. 7741. Springer, 369--381.
[43]
Jan Rutten, Adolfo Ballester-Bolinches, and Enric Cosme-Llópez. 2013. Varieties and Covarieties of Languages (Extended Abstract). Electr. Notes Theor. Comput. Sci. 298 (2013), 7--28.
[44]
Jan J. M. M. Rutten. 2000. Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249, 1 (2000), 3--80.
[45]
Lutz Schröder and Dirk Pattinson. 2011. Description Logics and Fuzzy Probability. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16--22, 2011, Toby Walsh (Ed.). IJCAI/AAAI, 1075--1081. http://ijcai.org/papers11/Papers/IJCAI11-184.pdf
[46]
Lutz Schröder and Yde Venema. 2010. Flat Coalgebraic Fixed Point Logics, See Gastin and Laroussinie {2010}, 524--538.
[47]
Marcel Paul Schützenberger. 1961. On the Definition of a Family of Automata. Information and Control 4, 2--3 (1961), 245--270.
[48]
Alexandra Silva. 2010. Kleene Coalgebra. Ph.D. Dissertation. Radboud University Nijmegen.
[49]
Alexandra Silva, Filippo Bonchi, Marcello M. Bonsangue, and Jan J. M. M. Rutten. 2013. Generalizing determinization from automata to coalgebras. Logical Methods in Computer Science 9, 1 (2013).
[50]
Sam Staton. 2015. Algebraic Effects, Linearity, and Quantum Programming Languages, See Rajamani and Walker {2015}, 395--406.
[51]
Sam Staton and Paul Blain Levy. 2013. Universal properties of impure programming languages, See Giacobazzi and Cousot {2013}, 179--192.
[52]
Natsuki Urabe and Ichiro Hasuo. 2014. Generic Forward and Backward Simulations III: Quantitative Simulations by Matrices, See Baldan and Gorla {2014}, 451--466.
[53]
Franck van Breugel and James Worrell. 2006. Approximating and computing behavioural distances in probabilistic transition systems. Theor. Comput. Sci. 360, 1--3 (2006), 373--385.
[54]
Joost Winter, Marcello M. Bonsangue, and Jan J. M. M. Rutten. 2013. Coalgebraic Characterizations of Context-Free Languages. Logical Methods in Computer Science 9, 3 (2013).
Index Terms
- A short introduction to the coalgebraic method
Recommendations
Categories of coalgebraic games
MFCS'12: Proceedings of the 37th international conference on Mathematical Foundations of Computer ScienceWe consider a general notion of coalgebraic game, whereby games are viewed as elements of a final coalgebra. This allows for a smooth definition of game operations (e.g. sum, negation, and linear implication) as final morphisms. The notion of ...
Finitary coalgebraic multisemilattices and multilattices
In this paper we continue the coalgebraization of the structure of multilattice. Specifically, we introduce a coalgebraic characterization of the notion of finitary multi (semi) lattice, a generalization of that of semilattice which arises naturally in ...
Functorial Coalgebraic Logic: The Case of Many-sorted Varieties
Following earlier work, a modal logic for T-coalgebras is a functor L on a suitable variety. Syntax and proof system of the logic are given by presentations of the functor. This paper makes two contributions. First, a previous result characterizing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2015
36 pages
Copyright © 2015 Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 April 2015
Published in SIGLOG Volume 2, Issue 2
Check for updates
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 261Total Downloads
- Downloads (Last 12 months)10
- Downloads (Last 6 weeks)1
Reflects downloads up to 28 Dec 2024
Other Metrics
Citations
Cited By
View all- Colcombet TPetrişan D(2017)Automata and minimizationACM SIGLOG News10.1145/3090064.30900664:2(4-27)Online publication date: 3-May-2017
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in