Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T03:37:34.706Z Has data issue: false hasContentIssue false
  • English
  • Français

Finitary monads on the category of posets

Published online by Cambridge University Press:  26 November 2021

Jiří Adámek ,
Chase Ford Open the ORCID record for Chase Ford [Opens in a new window] ,
Stefan Milius Open the ORCID record for Stefan Milius [Opens in a new window]  and
Lutz Schröder Open the ORCID record for Lutz Schröder [Opens in a new window]
Jiří Adámek
Affiliation:
Department of Mathematics, Czech Technical University Prague, Prague, Czech Republic Institute of Theoretical Computer Science, Technische Universität Braunschweig, Brunswick, Germany
Chase Ford
Affiliation:
Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Erlangen, Germany
Stefan Milius*
Affiliation:
Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Erlangen, Germany
Lutz Schröder
Affiliation:
Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Erlangen, Germany
*
*Corresponding author. Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Finitary monads on Pos are characterized as precisely the free-algebra monads of varieties of algebras. These are classes of ordered algebras specified by inequations in context. Analogously, finitary enriched monads on Pos are characterized: here we work with varieties of coherent algebras which means that their operations are monotone.

Keywords

Posetsmonadalgebraic theory
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 31 , Special Issue 7: The Power Festschrift , August 2021 , pp. 799 - 821
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Footnotes

†

Supported by the Grant Agency of the Czech Republic under the grant 19-00902S.

‡

Supported by the Deutsche Forschungsgemeinschaft (DFG) within the Research and Training Group 2475 “Cybercrime and Forensic Computing” (393541319/GRK2475/1-2019).

§

Supported by the Deutsche Forschungsgemeinschaft (DFG) under project MI 717/7-1.

Supported by the Deutsche Forschungsgemeinschaft (DFG) under project SCHR 1118/6-2.

References

Adámek, J. (1974). Free algebras and automata realizations in the language of categories. Commentationes Mathematicae Universitatis Carolinae 15 (4) 589–602.Google Scholar
Adámek, J., Dostál, M. and Velebil, J. (2021). A categorical view of varieties of ordered algebras. Mathematical Structures in Computer Science, special issue in honor of John Power, to appear, available at https://arxiv.org/abs/2011.13839.Google Scholar
Adámek, J. and Rosický, J. (1994). Locally Presentable and Accessible Categories, Cambridge University Press.CrossRefGoogle Scholar
Barr, M. (1970). Coequalizers and free triples. Mathematische Zeitschrift 116 (4) 307–322.CrossRefGoogle Scholar
Bird, R. (1984). Limits in 2-Categories of Locally Presentened Categories. Phd thesis, University of Sydney.Google Scholar
Bloom, S. (1976). Varieties of ordered algebras. Journal of Computer and System Sciences 2 (13) 200–212.CrossRefGoogle Scholar
Bloom, S. and Wright, J. (1983). P-varieties – a signature independent characterization of varieties of ordered algebras. Journal of Pure and Applied Algebra 29 (1) 13–58.CrossRefGoogle Scholar
Borceux, F. (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures, Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
Ford, C., Milius, S. and Schröder, L. (2021a). Behavioural preorders via graded monads. In: Libkin, L. (ed.) Logic in Computer Science, LICS 2021, IEEE, 1–13. Full version available at https://arxiv.org/abs/2011.14339.CrossRefGoogle Scholar
Ford, C., Milius, S. and Schröder, L. (2021b). Monads on categories of relational structures. In: Gadducci, F. and Silva, A. (eds.) Algebra and Coalgebra in Computer Science, CALCO 2021, LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik. To appear. Full version available as arXiv e-print 2107.03880.Google Scholar
Jones, C. and Plotkin, G. (1989). A probabilistic powerdomain of evaluations. In: Parikh, R. (ed.) Logic in Computer Science, LICS 1989, IEEE Computer Society, 186–195.CrossRefGoogle Scholar
Kelly, G.M. (1980). A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on. Bulletin of the Australian Mathematical Society 22 (1) 1–83.CrossRefGoogle Scholar
Kelly, G.M. and Lack, S. (1993). Finite product-preserving functors, Kan extensions, and strongly-finitary 2-monads. Applied Categorical Structures 1 (1) 85–94.CrossRefGoogle Scholar
Kelly, G.M. and Power, A.J. (1993). Adjunctions whose counits are coequalizers, and presentations of finitary enriched monads. Journal of Pure and Applied Algebra 15 (3) 163–179.CrossRefGoogle Scholar
Kurz, A. and Velebil, J. (2017). Quasivarieties and varieties of ordered algebras: regularity and exactness. Mathematical Structures in Computer Science 27 (7) 1153–1194.CrossRefGoogle Scholar
Lack, S. (1999). On the monadicity of finitary monads. Journal of Pure and Applied Algebra 140 (1) 65–73.CrossRefGoogle Scholar
Linton, F. (1969). An outline of functorial semantics. In: Eckmann, B. (ed.) Seminar on Triples and Categorical Homology Theory, Lecture Notes in Mathematics, vol. 80, Springer, 7–52.CrossRefGoogle Scholar
MacLane, S. (1998). Categories for the Working Mathematician, 2nd ed., Springer.Google Scholar
Manes, E. (1976). Algebraic Theories, Springer.CrossRefGoogle Scholar
Mardare, R., Panangaden, P. and Plotkin, G. (2016). Quantitative algebraic reasoning. In: Grohe, M., Koskinen, E. and Shankar, N. (eds.) Logic in Computer Science, LICS 2016, ACM, 700–709.Google Scholar
Mardare, R., Panangaden, P. and Plotkin, G. (2017). On the axiomatizability of quantitative algebras. In: Ouaknine, J. (ed.) Logic in Computer Science, LICS 2017, IEEE Computer Society, 1–12.CrossRefGoogle Scholar
Milius, S. and Urbat, H. (2019). Equational axiomatization of algebras with structure. In: Bojańczyk, M. and Simpson, A. (eds.) Foundations of Software Science and Computation Structures, FOSSACS 2019, Lecture Notes in Computer Science, vol. 11425, Springer, 400–417.CrossRefGoogle Scholar
Moggi, E. (1991). Notions of computations and monads. Information & Computation 93 (1) 55–92.CrossRefGoogle Scholar
Nishizawa, K. and Power, A.J. (2009). Lawvere theories enriched over a general base. Journal of Pure and Applied Algebra 213 (3) 377–386.CrossRefGoogle Scholar
Plotkin, G. and Power, A.J. (2001). Semantics for algebraic operations. In: Brookes, S. D. and Mislove, M. W. (eds.) Mathematical Foundations of Programming Semantics, MFPS 2001, ENTCS, vol. 45, Elsevier, 332–345.Google Scholar
Plotkin, G. and Power, A.J. (2002). Notions of computation determine monads. In: Nielsen, M. and Engberg, U. (eds.) Foundations of Software Science and Computation Structures, FOSSACS 2002, LNCS, vol. 2303, Springer, 342–356.CrossRefGoogle Scholar
Power, A.J. (1999). Enriched Lawvere theories. Theory and Applications of Categories 6 (7) 83–93.Google Scholar
Power, A.J. (2005). Discrete Lawvere theories. In: Fiadeiro, J. L., Harman, N., Roggenbach, M. and Rutten, J. J. M. M. (eds.) Algebra and Coalgebra in Computer Science, CALCO 2005, LNCS, vol. 3629, Springer, 348–363.Google Scholar
Pumplün, D. (2003). Positively convex modules and ordered normed linear spaces. Journal of Convex Analysis 10 (1) 109–128.Google Scholar
Pumplün, D. and Röhrl, H. (1984). Banach spaces and totally convex spaces I. Communications in Algebra 12 (8) 953–1019.CrossRefGoogle Scholar
Rosický, J. (2021). Metric monads. Submitted, available at https://arxiv.org/abs/2012.14641.Google Scholar
Trnková, V., Adámek, J., Koubek, V. and Reiterman, V. (1975). Free algebras, input processes and free monads. Commentationes Mathematicae Universitatis Carolinae 16 (2) 339–351.Google Scholar