article

Stone coalgebras

Authors:

Alexander Kurz,

Yde VenemaAuthors Info & Claims

Theoretical Computer Science, Volume 327, Issue 1-2

Pages 109 - 134

https://doi.org/10.1016/j.tcs.2004.07.023

Published: 25 October 2004 Publication History

Abstract

We argue that the category of Stone spaces forms an interesting base category for coalgebras, in particular, if one considers the Vietoris functor as an analogue to the power set functor on the category of sets.We prove that the so-called descriptive general frames, which play a fundamental role in the semantics of modal logics, can be seen as Stone coalgebras in a natural way. This yields a duality between modal algebras and coalgebras for the Vietoris functor.Building on this idea, we introduce the notion of a Vietoris polynomial functor over the category of Stone spaces. For each such functor T we provide an adjunction between T-sorted Boolean algebras with operators and the Stone coalgebras for T. We also identify the subcategory of algebras on which the adjunction restricts to an equivalence and show that the final T-coalgebra is the dual of the initial T-BAO.

References

[1]

{1} S. Abramsky, A Cook's tour of the finitary non-well-founded sets, Invited Lecture at BCTCS, 1988.]]

[2]

{2} S. Abramsky, A domain equation for bisimulation, Inform. Comput. 92 (2) (1991) 161-218.]]

[3]

{3} S. Abramsky, Domain theory in logical form, Ann. Pure Appl. Logic 51 (1991) 1-77.]]

[4]

{4} S. Abramsky, A. Jung, Domain theory, S. Abramsky, D. Gabbay, T.S.E. Maibaum (Eds.), Handbook of Logic in Computer Science, Vol. 3, Oxford University Press, Oxford, 1994, pp. 1-168.]]

Digital Library

[5]

{5} F. Alessi, P. Baldan, E Honsell, Partializing stone spaces using SFP domains (extended abstract), M. Bidoit et al.(Ed.), CAAP'97, Lecture Notes in Computer Science, Vol. 1158, Springer, Berlin, 1997, pp. 478-489.]]

Digital Library

[6]

{6} A. Baltag, A logic for coalgebraic simulation, H. Reichel(Ed.), Coalgebraic Methods in Computer Science (CMCS'00), Electronic Notes in Theoretical Computer Science, Vol. 33, 2000.]]

[7]

{7} F. Bartels, A. Sokolova, E. de Vink, A hierarchy of probabilistic system types, H.P. Gumm(Ed.), Coalgebraic Methods in Computer Science (CMCS'03), Electronic Notes in Theoretical Computer Science, Vol. 86.1, 2003.]]

Digital Library

[8]

{8} P. Blackburn, M. de Rijke, Y. Venema, Modal Logic, Cambridge University Press, Cambridge, 2001.]]

Digital Library

[9]

{9} C. Cîrstea, On specification logics for algebra-coalgebra structures: reconciling reachability and observability, M. Nielsen(Ed.), Proc. FoSSaCS 2002, Lecture Notes in Computer Science, Vol. 2303, Springer, Berlin, 2002, pp. 82-97.]]

Digital Library

[10]

{10} B. Davey, J. Galati, A coalgebraic view of Heyting duality, Studia Logica 75 (2003) 259-270.]]

[11]

{11} J. deBakker, E. deVink, Control Flow Semantics, MIT Press, Cambridge, MA, 1996.]]

Digital Library

[12]

{12} R. Engelking, General Topology, Heldermann Verlag, 1989.]]

[13]

{13} L.L. Esakia, Topological Kripke models, Soviet Math. Doklady 15 (1974) 147-151.]]

[14]

{14} M. Gehrke, The order structure of stone spaces and the Td-separation axiom, Zeitschrift fOr Mathematische Logik und Grundlagen der Mathematik 37 (1991) 5-15.]]

[15]

{15} R. Goldblatt, Metamathematics of modal logic I, Rep. Math. Logic 6 (1976) 41-78.]]

[16]

{16} R. Goldblatt, A calculus of terms for coalgebras of polynomial functors, A. Corradini, M. Lenisa, U. Montanari (Eds.), Coalgebraic Methods in Computer Science (CMCS'01), Electronic Notes in Theoretical Computer Science, Vol. 44, 2001.]]

[17]

{17} B. Jacobs, Many-sorted coalgebraic modal logic: a model-theoretic study, Theoret. Inform. and Appl. 35 (1) (2001) 31-59.]]

[18]

{18} P. Johnstone, Stone Spaces, Cambridge University Press, Cambridge, 1982.]]

[19]

{19} A. Kurz, Logics for coalgebras and applications to computer science, Ph.D. Thesis, Ludwig-Maximilians-Universität München, 2000.]]

[20]

{20} A. Kurz, A co-variety-theorem for modal logic, in: M. Zakharyaschev et al. (Eds.), Advances in Modal Logic 2, CSLI, Stanford University, Stanford, 2001.]]

[21]

{21} A. Kurz, D. Pattinson, Coalgebraic modal logic of finite rank, Math. Struct. Comput. Sci., Forthcoming.]]

Digital Library

[22]

{22} A. Kurz, J. Rosický, Modal predicates and coequations, L. Moss(Ed.), Coalgebraic Methods in Computer Science (CMCS'2002), Electronic Notes in Theoretical Computer Science, Vol. 65, 2002.]]

[23]

{23} S. Mac Lane, Category Theory for the Working Mathematician, Springer, Berlin, 1971.]]

[24]

{24} E. Michael, Topologies on spaces of subsets, Trans. Amer. Math. Soc. 71 (1951) 152-182.]]

[25]

{25} L. Moss, Coalgebraic logic, Ann. Pure Appl. Logic 96 (1999) 277-317.]]

[26]

{26} A. Palmigiano, Coalgebraic semantics for positive modal logic, H.-P. Gumm(Ed.), Coalgebraic Methods in Computer Science (CMCS'03), Electronic Notes in Theoretical Computer Science, Vol. 82, 2003.]]

[27]

{27} D. Pattinson, Semantical principles in the modal logic of coalgebras, Proc. STACS 2001, Lecture Notes in Computer Science, Vol. 2010, Springer, Berlin, 2001, pp. 514-526.]]

Digital Library

[28]

{28} M. Rößiger, Coalgebras and modal logic, H. Reichel(Ed.), Coalgebraic Methods in Computer Science (CMCS'00), Electronic Notes in Theoretical Computer Science, Vol. 33, 2000.]]

[29]

{29} J. Rutten, A calculus of transition systems (towards universal coalgebra), A. Ponse, M. deRijke, Y. Venema (Eds.), Modal Logic and Process Algebra, CSLI Lecture Notes, Vol. 53, CSLI, Stanford University, Stanford, 1995.]]

[30]

{30} J. Rutten, Universal coalgebra: a theory of systems, Theoret. Comput. Sci. 249 (2000) 3-80.]]

Digital Library

[31]

{31} G. Sambin, V. Vaccaro, Topology and duality in modal logic, Ann. Pure Appl. Logic 37 (1988) 249-296.]]

[32]

{32} D. Tuff, J. Rutten, On the foundations of final coalgebra semantics: non-well-founded sets, partial orders, metric spaces, Math. Struct. Comput. Sci. 8 (1998).]]

Digital Library

[33]

{33} S.J. Vickers, Topology Via Logic, Cambridge University Press, Cambridge, 1989.]]

Digital Library

[34]

{34} J. Worrell, Terminal sequences for accessible endofunctors, B. Jacobs, J. Rutten (Eds.), Coalgebraic Methods in Computer Science (CMCS'99), Electronic Notes in Theoretical Computer Science, Vol. 19, 1999.]]

Cited By

Verity FMaruyama Y(2024)Modal Hyperdoctrine: Higher-Order and Non-normal ExtensionsLogic, Language, Information, and Computation10.1007/978-3-031-62687-6_15(225-242)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62687-6_15
Birkmann FUrbat HMilius S(2024)Monoidal Extended Stone DualityFoundations of Software Science and Computation Structures10.1007/978-3-031-57228-9_8(144-165)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57228-9_8
de Groot J(2021)Positive Monotone Modal LogicStudia Logica10.1007/s11225-020-09928-9109:4(829-857)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s11225-020-09928-9
Show More Cited By

Index Terms

Stone coalgebras

Recommendations

Algebraic Semantics for Coalgebraic Logics

With coalgebras usually being defined in terms of an endofunctor T on sets, this paper shows that modal logics for T-coalgebras can be naturally described as functors L on boolean algebras. Building on this idea, we study soundness, completeness and ...
Final coalgebras for functors on measurable spaces
Special issue: Seventh workshop on coalgebraic methods in computer science 2004

We prove that every functor on the category Meas of measurable spaces built from the identity and constant functors using products, coproducts, and the probability measure functor @D has a final coalgebra. Our work builds on the construction of the ...
On Coalgebras over Algebras

We extend Barr's well-known characterization of the final coalgebra of a Set-endofunctor as the completion of its initial algebra to the Eilenberg-Moore category of algebras for a Set-monad M for functors arising as liftings. As an application we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 327, Issue 1-2

Selected papers of CMCS'03

25 October 2004

219 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 25 October 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Verity FMaruyama Y(2024)Modal Hyperdoctrine: Higher-Order and Non-normal ExtensionsLogic, Language, Information, and Computation10.1007/978-3-031-62687-6_15(225-242)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62687-6_15
Birkmann FUrbat HMilius S(2024)Monoidal Extended Stone DualityFoundations of Software Science and Computation Structures10.1007/978-3-031-57228-9_8(144-165)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57228-9_8
de Groot J(2021)Positive Monotone Modal LogicStudia Logica10.1007/s11225-020-09928-9109:4(829-857)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s11225-020-09928-9
Nganteu CKianpi MLele C(2021)On MV-coalgebras over the category of BL-algebrasSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-021-06082-925:20(12805-12815)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00500-021-06082-9
Das LRay K(2021)Bitopological duality for algebras of Fitting’s logic and natural duality extensionActa Informatica10.1007/s00236-020-00384-558:5(571-584)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00236-020-00384-5
de Groot JPattinson DHermanns HZhang LKobayashi NMiller D(2020)Modal Intuitionistic Logics as Dialgebraic LogicsProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3373718.3394807(355-369)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3373718.3394807
Bezhanishvili NEnqvist Sde Groot J(2020)Duality for Instantial Neighbourhood Logic via CoalgebraCoalgebraic Methods in Computer Science10.1007/978-3-030-57201-3_3(32-54)Online publication date: 25-Apr-2020
https://dl.acm.org/doi/10.1007/978-3-030-57201-3_3
Nishizawa KKatsumata SKomorida Y(2020)Stone Dualities from OpfibrationsRelational and Algebraic Methods in Computer Science10.1007/978-3-030-43520-2_14(221-236)Online publication date: 26-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-43520-2_14
Maruyama Y(2020)Higher-Order Categorical Substructural Logic: Expanding the Horizon of Tripos TheoryRelational and Algebraic Methods in Computer Science10.1007/978-3-030-43520-2_12(187-203)Online publication date: 26-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-43520-2_12
Kupke C(2018)Coalgebraic Logics & DualityCoalgebraic Methods in Computer Science10.1007/978-3-030-00389-0_2(6-12)Online publication date: 14-Apr-2018
https://dl.acm.org/doi/10.1007/978-3-030-00389-0_2
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents