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. DOI: http://dx.doi.org/10.1145/2429069.2429075
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. DOI: http://dx.doi.org/10.1007/978-3-642-54830-7_24
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. DOI: http://dx.doi.org/10.1016/j.entcs.2014.10.002
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. DOI: http://dx.doi.org/10.1145/2535838.2535862
5. Dana Angluin. 1987. Learning Regular Sets from Queries and Counterexamples. Inf. Comput. 75, 2 (1987), 87--106. DOI: http://dx.doi.org/10.1016/0890-5401(87)90052-6
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. DOI: http://dx.doi.org/10.1007/978-3-642-36742-7_1
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. DOI: http://dx.doi.org/10.1007/978-3-662-44584-6
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. DOI: http://dx.doi.org/10.1007/978-3-642-32621-9_14
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. DOI: http://dx.doi.org/10.1016/j.entcs.2012.08.006
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. DOI: http://dx.doi.org/10.1145/2490818
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. DOI: http://dx.doi.org/10.1007/978-3-642-29485-3_2
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. DOI: http://dx.doi.org/10.1007/978-3-319-03542-0_1
14. Filippo Bonchi and Damien Pous. 2013. Checking NFA equivalence with bisimulations up to congruence, See Giacobazzi and Cousot {2013}, 457--468. DOI: http://dx.doi.org/10.1145/2429069.2429124
15. Filippo Bonchi and Damien Pous. 2015. Hacking nondeterminism with induction and coinduction. Commun. ACM 58, 2 (2015), 87--95. DOI: http://dx.doi.org/10.1145/2713167
16. Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. 2015. Full Abstraction for Signal Flow Graphs, See Rajamani and Walker {2015}, 515--526. DOI: http://dx.doi.org/10.1145/2676726.2676993
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. DOI: http://dx.doi.org/10.1145/2422085.2422092
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. DOI: http://dx.doi.org/10.1007/978-3-642-04081-8_12
19. Pavol Cerný, Thomas A. Henzinger, and Arjun Radhakrishna. 2010. Simulation Distances, See Gastin and Laroussinie {2010}, 253--268. DOI: http://dx.doi.org/10.1007/978-3-642-15375-4_18
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. DOI: http://dx.doi.org/10.1093/comjnl/bxp004
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. DOI: http://dx.doi.org/10.1007/3-540-48320-9_19
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. DOI: http://dx.doi.org/10.1007/978-3-642-36976-6_14
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. DOI: http://dx.doi.org/10.1145/2676726.2677011
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. DOI: http://dx.doi.org/10.1007/978-3-642-15375-4
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. DOI: http://dx.doi.org/10.1007/978-3-662-44602-7_21
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. DOI: http://dx.doi.org/10.1007/978-3-642-14203-1_5
28. Ichiro Hasuo. 2010. Generic Forward and Backward Simulations II: Probabilistic Simulation, See Gastin and Laroussinie {2010}, 447--461. DOI: http://dx.doi.org/10.1007/978-3-642-15375-4_31
29. Bart Jacobs, Milad Niqui, Jan J. M. M. Rutten, and Alexandra Silva. 2011. Preface. Theor. Comput. Sci. 412, 38 (2011), 4967--4968. DOI: http://dx.doi.org/10.1016/j.tcs.2011.06.001
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. DOI: http://dx.doi.org/10.1007/978-3-319-06880-0_20
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. DOI: http://dx.doi.org/10.1007/978-3-642-37036-6_4
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. DOI: http://dx.doi.org/10.1007/978-3-642-32940-1_29
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. DOI: http://dx.doi.org/10.1007/978-3-662-43951-7_23
35. Dexter Kozen. 1997. Kleene Algebra with Tests. ACM Trans. Program. Lang. Syst. 19, 3 (1997), 427--443. DOI: http://dx.doi.org/10.1145/256167.256195
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. DOI: http://dx.doi.org/10.1007/978-3-662-44584-6_8
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. DOI: http://dx.doi.org/10.1007/978-3-540-24727-2_28
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. DOI: http://dx.doi.org/10.1007/978-3-642-35843-2_32
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. DOI: http://dx.doi.org/10.1016/j.entcs.2013.09.005
44. Jan J. M. M. Rutten. 2000. Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249, 1 (2000), 3--80. DOI: http://dx.doi.org/10.1016/S0304-3975(00)00056-6
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. DOI: http://dx.doi.org/10.1007/978-3-642-15375-4_36
47. Marcel Paul Schützenberger. 1961. On the Definition of a Family of Automata. Information and Control 4, 2--3 (1961), 245--270. DOI: http://dx.doi.org/10.1016/S0019-9958(61)80020-X
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). DOI: http://dx.doi.org/10.2168/LMCS-9(1:9)2013
50. Sam Staton. 2015. Algebraic Effects, Linearity, and Quantum Programming Languages, See Rajamani and Walker {2015}, 395--406. DOI: http://dx.doi.org/10.1145/2676726.2676999
51. Sam Staton and Paul Blain Levy. 2013. Universal properties of impure programming languages, See Giacobazzi and Cousot {2013}, 179--192. DOI: http://dx.doi.org/10.1145/2429069.2429091
52. Natsuki Urabe and Ichiro Hasuo. 2014. Generic Forward and Backward Simulations III: Quantitative Simulations by Matrices, See Baldan and Gorla {2014}, 451--466. DOI: http://dx.doi.org/10.1007/978-3-662-44584-6_31
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. DOI: http://dx.doi.org/10.1016/j.tcs.2006.05.021
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). DOI: http://dx.doi.org/10.2168/LMCS-9(3:14)2013

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Mathematics and statistics

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Computer algebra systems

    • Representation of mathematical objects