Thin Coalgebraic Behaviours Are Inductive
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910989991018496 |
|---|---|
| author | Chernev, Anton Cîrstea, Corina Hansen, Helle Hvid Kupke, Clemens |
| author_facet | Chernev, Anton Cîrstea, Corina Hansen, Helle Hvid Kupke, Clemens |
| contents | Coalgebras for analytic functors uniformly model graph-like systems where the successors of a state may admit certain symmetries. Examples of successor structure include ordered tuples, cyclic lists and multisets. Motivated by goals in automata-based verification and results on thin trees, we introduce thin coalgebras as those coalgebras with only countably many infinite paths from each state. Our main result is an inductive characterisation of thinness via an initial algebra. To this end, we develop a syntax for thin behaviours and capture with a single equation when two terms represent the same thin behaviour. Finally, for the special case of polynomial functors, we retrieve from our syntax the notion of Cantor-Bendixson rank of a thin tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07013 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Thin Coalgebraic Behaviours Are Inductive Chernev, Anton Cîrstea, Corina Hansen, Helle Hvid Kupke, Clemens Formal Languages and Automata Theory Coalgebras for analytic functors uniformly model graph-like systems where the successors of a state may admit certain symmetries. Examples of successor structure include ordered tuples, cyclic lists and multisets. Motivated by goals in automata-based verification and results on thin trees, we introduce thin coalgebras as those coalgebras with only countably many infinite paths from each state. Our main result is an inductive characterisation of thinness via an initial algebra. To this end, we develop a syntax for thin behaviours and capture with a single equation when two terms represent the same thin behaviour. Finally, for the special case of polynomial functors, we retrieve from our syntax the notion of Cantor-Bendixson rank of a thin tree. |
| title | Thin Coalgebraic Behaviours Are Inductive |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2504.07013 |