Document Open Access Logo

Minimality Notions via Factorization Systems ((Co)algebraic pearls)

Author Thorsten Wißmann

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2021.24.pdf
  • Filesize: 0.79 MB
  • 21 pages

Document Identifiers

Author Details

Thorsten Wißmann
  • Radboud University Nijmegen, The Netherlands

Funding

Supported by the NWO TOP project 612.001.852.

Acknowledgements

The author thanks Stefan Milius and Jurriaan Rot for inspiring discussions and thanks the referees for their helpful comments.

Cite AsGet BibTex

Thorsten Wißmann. Minimality Notions via Factorization Systems ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CALCO.2021.24

Abstract

For the minimization of state-based systems (i.e. the reduction of the number of states while retaining the system’s semantics), there are two obvious aspects: removing unnecessary states of the system and merging redundant states in the system. In the present article, we relate the two aspects on coalgebras by defining an abstract notion of minimality. The abstract notion minimality and minimization live in a general category with a factorization system. We will find criteria on the category that ensure uniqueness, existence, and functoriality of the minimization aspects. The proofs of these results instantiate to those for reachability and observability minimization in the standard coalgebra literature. Finally, we will see how the two aspects of minimization interact and under which criteria they can be sequenced in any order, like in automata minimization.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Coalgebra
  • Reachability
  • Observability
  • Minimization
  • Factorization System

Metrics

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

Related Versions

References

  1. Peter Aczel and Nax Mendler. A final coalgebra theorem. In Proc. Category Theory and Computer Science (CTCS), volume 389 of Lecture Notes Comput. Sci., pages 357-365. Springer, 1989. Google Scholar
  2. Jiří Adámek, Horst Herrlich, and George E. Strecker. Abstract and Concrete Categories: The Joy of Cats. Dover Publications, 2nd edition, 2009. Google Scholar
  3. Jiří Adámek, Stefan Milius, and Lawrence S. Moss. Fixed points of functors. Journal of Logical and Algebraic Methods in Programming, 95:41-81, 2018. Google Scholar
  4. Jiří Adámek, Stefan Milius, Lawrence S. Moss, and Lurdes Sousa. Well-pointed coalgebras. Logical Methods in Computer Science, 9(3:2):51 pp., 2013. Google Scholar
  5. Steve Awodey. Category Theory. Oxford Logic Guides. OUP Oxford, 2010. Google Scholar
  6. Adriana Balan and Alexander Kurz. Finitary functors: From set to preord and poset. In Andrea Corradini, Bartek Klin, and Corina Cîrstea, editors, Algebra and Coalgebra in Computer Science - 4th International Conference, CALCO 2011, Winchester, UK, August 30 - September 2, 2011. Proceedings, volume 6859 of Lecture Notes in Computer Science, pages 85-99. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22944-2_7.
  7. Simone Barlocco, Clemens Kupke, and Jurriaan Rot. Coalgebra learning via duality. In Mikolaj Bojanczyk and Alex Simpson, editors, Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings, volume 11425 of Lecture Notes in Computer Science, pages 62-79. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17127-8_4.
  8. Falk Bartels, Ana Sokolova, and Erik P. de Vink. A hierarchy of probabilistic system types. Theor. Comput. Sci., 327(1-2):3-22, 2004. URL: https://doi.org/10.1016/j.tcs.2004.07.019.
  9. Nick Bezhanishvili, Clemens Kupke, and Prakash Panangaden. Minimization via duality. In C.-H. Luke Ong and Ruy J. G. B. de Queiroz, editors, Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3-6, 2012. Proceedings, volume 7456 of Lecture Notes in Computer Science, pages 191-205. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32621-9_14.
  10. Michel Bidoit, Rolf Hennicker, and Alexander Kurz. On the duality between observability and reachability. In Furio Honsell and Marino Miculan, editors, Foundations of Software Science and Computation Structures, 4th International Conference (FOSSACS 2001), Held as Part of ETAPS 2001 Genova, Italy, April 2-6, 2001, Proceedings, volume 2030 of Lecture Notes in Computer Science, pages 72-87. Springer, 2001. URL: https://doi.org/10.1007/3-540-45315-6_5.
  11. Filippo Bonchi, Marcello M. Bonsangue, Helle Hvid Hansen, Prakash Panangaden, Jan J. M. M. Rutten, and Alexandra Silva. Algebra-coalgebra duality in brzozowski’s minimization algorithm. ACM Trans. Comput. Log., 15(1):3:1-3:29, 2014. URL: https://doi.org/10.1145/2490818.
  12. Salem Derisavi, Holger Hermanns, and William H. Sanders. Optimal state-space lumping in markov chains. Inf. Process. Lett., 87(6):309-315, 2003. URL: https://doi.org/10.1016/S0020-0190(03)00343-0.
  13. Ulrich Dorsch, Stefan Milius, Lutz Schröder, and Thorsten Wißmann. Efficient coalgebraic partition refinement. In Roland Meyer and Uwe Nestmann, editors, 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, volume 85 of LIPIcs, pages 32:1-32:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2017.32.
  14. Agostino Dovier, Carla Piazza, and Alberto Policriti. An efficient algorithm for computing bisimulation equivalence. Theor. Comput. Sci., 311(1-3):221-256, 2004. URL: https://doi.org/10.1016/S0304-3975(03)00361-X.
  15. Jan Friso Groote, Jan Martens, and Erik de Vink. Bisimulation by Partitioning Is Ω((m+n)log n). In Serge Haddad and Daniele Varacca, editors, 32nd International Conference on Concurrency Theory (CONCUR 2021), volume 203 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2021.31.
  16. H. Peter Gumm. Functors for coalgebras. Algebra Universalis, 45(2):135-147, April 2001. URL: https://doi.org/10.1007/s00012-001-8156-x.
  17. H. Peter Gumm. On minimal coalgebras. Applied Categorical Structures, 16(3):313-332, June 2008. URL: https://doi.org/10.1007/s10485-007-9116-1.
  18. H. Peter Gumm and Tobias Schröder. Monoid-labeled transition systems. In Coalgebraic Methods in Computer Science, CMCS 2001, volume 44(1) of ENTCS, pages 185-204. Elsevier, 2001. URL: https://doi.org/10.1016/S1571-0661(04)80908-3.
  19. H. Peter Gumm and Tobias Schröder. Types and coalgebraic structure. algebra universalis, 53(2):229-252, 2005. URL: https://doi.org/10.1007/s00012-005-1888-2.
  20. Ichiro Hasuo, Bart Jacobs, and Ana Sokolova. Generic trace theory. In Neil Ghani and John Power, editors, Proceedings of the Eighth Workshop on Coalgebraic Methods in Computer Science, CMCS 2006, Vienna, Austria, March 25-27, 2006, volume 164 of Electronic Notes in Theoretical Computer Science, pages 47-65. Elsevier, 2006. URL: https://doi.org/10.1016/j.entcs.2006.06.004.
  21. John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Theory of Machines and Computations, pages 189-196. Academic Press, 1971. Google Scholar
  22. Thomas Ihringer. Algemeine Algebra. Mit einem Anhang über Universelle Coalgebra von H. P. Gumm, volume 10 of Berliner Studienreihe zur Mathematik. Heldermann Verlag, 2003. Google Scholar
  23. Bartek Klin and Vladimiro Sassone. Structural operational semantics for stochastic and weighted transition systems. Inf. Comput., 227:58-83, 2013. URL: https://doi.org/10.1016/j.ic.2013.04.001.
  24. Barbara König and Sebastian Küpper. Generic partition refinement algorithms for coalgebras and an instantiation to weighted automata. In Josep Díaz, Ivan Lanese, and Davide Sangiorgi, editors, Theoretical Computer Science - 8th IFIP TC 1/WG 2.2 International Conference, TCS 2014, Rome, Italy, September 1-3, 2014. Proceedings, volume 8705 of Lecture Notes in Computer Science, pages 311-325. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44602-7_24.
  25. Alexander Kurz. Logics for Coalgebras and Applications to Computer Science. PhD thesis, Ludwig-Maximilians-Universität München, July 2000. URL: https://www.cs.le.ac.uk/people/akurz/LMU/Diss/all-s.ps.gz.
  26. Alexander Kurz, Daniela Petrisan, Paula Severi, and Fer-Jan de Vries. Nominal coalgebraic data types with applications to lambda calculus. Log. Methods Comput. Sci., 9(4), 2013. URL: https://doi.org/10.2168/LMCS-9(4:20)2013.
  27. Stefan Milius, Dirk Pattinson, and Thorsten Wißmann. A new foundation for finitary corecursion and iterative algebras. Information and Computation, page 104456, September 2019. URL: https://doi.org/10.1016/j.ic.2019.104456.
  28. Stefan Milius, Lutz Schröder, and Thorsten Wißmann. Regular behaviours with names - on rational fixpoints of endofunctors on nominal sets. Appl. Categorical Struct., 24(5):663-701, 2016. URL: https://doi.org/10.1007/s10485-016-9457-8.
  29. Robert Paige and Robert Endre Tarjan. Three partition refinement algorithms. SIAM J. Comput., 16(6):973-989, 1987. URL: https://doi.org/10.1137/0216062.
  30. Jurriaan Rot. Coalgebraic minimization of automata by initiality and finality. In Lars Birkedal, editor, The Thirty-second Conference on the Mathematical Foundations of Programming Semantics, MFPS 2016, Carnegie Mellon University, Pittsburgh, PA, USA, May 23-26, 2016, volume 325 of Electronic Notes in Theoretical Computer Science, pages 253-276. Elsevier, 2016. URL: https://doi.org/10.1016/j.entcs.2016.09.042.
  31. Jan J. M. M. Rutten. Universal coalgebra: a theory of systems. Theor. Comput. Sci., 249(1):3-80, 2000. URL: https://doi.org/10.1016/S0304-3975(00)00056-6.
  32. Věra Trnková. On a descriptive classification of set functors I. Commentationes Mathematicae Universitatis Carolinae, 12(1):143-174, 1971. Google Scholar
  33. Daniele Turi and Gordon D. Plotkin. Towards a mathematical operational semantics. In Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29 - July 2, 1997, pages 280-291. IEEE Computer Society, 1997. URL: https://doi.org/10.1109/LICS.1997.614955.
  34. Antti Valmari. Bisimilarity minimization in o(m logn) time. In Giuliana Franceschinis and Karsten Wolf, editors, Applications and Theory of Petri Nets, 30th International Conference, PETRI NETS 2009, Paris, France, June 22-26, 2009. Proceedings, volume 5606 of Lecture Notes in Computer Science, pages 123-142. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02424-5_9.
  35. Antti Valmari and Giuliana Franceschinis. Simple O(m logn) time markov chain lumping. In Javier Esparza and Rupak Majumdar, editors, Tools and Algorithms for the Construction and Analysis of Systems, 16th International Conference, TACAS 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20-28, 2010. Proceedings, volume 6015 of Lecture Notes in Computer Science, pages 38-52. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-12002-2_4.
  36. Thorsten Wißmann, Ulrich Dorsch, Stefan Milius, and Lutz Schröder. Efficient and modular coalgebraic partition refinement. Log. Methods Comput. Sci., 16(1), 2020. URL: https://doi.org/10.23638/LMCS-16(1:8)2020.
  37. Thorsten Wißmann, Jérémy Dubut, Shin-ya Katsumata, and Ichiro Hasuo. Path category for free - open morphisms from coalgebras with non-deterministic branching. In Mikolaj Bojanczyk and Alex Simpson, editors, Foundations of Software Science and Computation Structures - 22nd International Conference (FOSSACS 2019), Held as Part of ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings, volume 11425 of Lecture Notes in Computer Science, pages 523-540. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17127-8_30.
  38. Thorsten Wißmann. Coalgebraic Semantics and Minimization in Sets and Beyond. Phd thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), 2020. URL: https://opus4.kobv.de/opus4-fau/frontdoor/index/index/docId/14222.
  39. Thorsten Wißmann, Stefan Milius, Shin-ya Katsumata, and Jérémy Dubut. A coalgebraic view on reachability. Commentationes Mathematicae Universitatis Carolinae, 60:4:605-638, December 2019. URL: https://doi.org/10.14712/1213-7243.2019.026.
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