DROPS

Document

(Co)algebraic pearl

DOI: 10.4230/LIPIcs.CALCO.2025.15

Trees in Coalgebra from Generalized Reachability ((Co)algebraic pearl)

Authors: Thorsten Wißmann, Bálint Kocsis, Jurriaan Rot, and Ruben Turkenburg

Published in: LIPIcs, Volume 342, 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025)

Abstract

An automaton is called reachable if every state is reachable from the initial state. This notion has been generalized coalgebraically in two ways: first, via a universal property on pointed coalgebras, namely, that a reachable coalgebra has no proper subcoalgebra; and second, a coalgebra is reachable if it arises as the union of an iterative computation of successor states, starting from the initial state. In the current paper, we present corresponding universal properties and iterative constructions for trees. The universal property captures when a coalgebra is a tree, namely, when it has no proper tree unravelling. The iterative construction unravels an arbitrary coalgebra to a tree. We show that this yields the expected notion of tree for a variety of standard examples. We obtain our characterization of trees by first generalizing the previous theory of reachable coalgebras. Surprisingly, both the universal property and the iterative construction for trees arise as an instance of this generalized notion of reachability.

Cite as

Thorsten Wißmann, Bálint Kocsis, Jurriaan Rot, and Ruben Turkenburg. Trees in Coalgebra from Generalized Reachability ((Co)algebraic pearl). In 11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 342, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wimann_et_al:LIPIcs.CALCO.2025.15,
  author =	{Wi{\ss}mann, Thorsten and Kocsis, B\'{a}lint and Rot, Jurriaan and Turkenburg, Ruben},
  title =	{{Trees in Coalgebra from Generalized Reachability}},
  booktitle =	{11th Conference on Algebra and Coalgebra in Computer Science (CALCO 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-383-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{342},
  editor =	{C\^{i}rstea, Corina and Knapp, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2025.15},
  URN =		{urn:nbn:de:0030-drops-235740},
  doi =		{10.4230/LIPIcs.CALCO.2025.15},
  annote =	{Keywords: Trees, Coalgebra, Factorization Systems}
}

Search Results

Documents authored by Kocsis, Bálint

Trees in Coalgebra from Generalized Reachability ((Co)algebraic pearl)

Abstract

Cite as

Thanks for your feedback!

Could not send message