Unambiguous acceptance of thin coalgebras

Tools

Chernev, Anton and Cirstea, Corina and Hansen, Helle Hvid and Kupke, Clemens; (2025) Unambiguous acceptance of thin coalgebras. In: Proceedings of MFPS XLI. Electronic Notes in Theoretical Informatics and Computer Science . INRIA, p. 27. (https://doi.org/10.46298/entics.16832)

[thumbnail of Chernev-etal-ENTICS-2025-Unambiguous-acceptance-of-thin-coalgebras]
Preview
 Text. Filename: Chernev-etal-ENTICS-2025-Unambiguous-acceptance-of-thin-coalgebras.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (866kB)| Preview

Abstract

Automata admitting at most one accepting run per structure, known as unambiguous automata, find applications in verification of reactive systems as they extend the class of deterministic automata whilst maintaining some of their desirable properties. In this paper, we generalise a classical construction of unambiguous automata from thin trees to thin coalgebras for analytic functors. This achieves two goals: extending the existing construction to a larger class of structures, and providing conceptual clarity and parametricity to the construction by formalising it in the coalgebraic framework. As part of the construction, we link automaton acceptance of languages of thin coalgebras to language recognition via so-called coherent algebras, which were previously introduced for studying thin coalgebras. This link also allows us to establish an automata-theoretic characterisation of languages recognised by finite coherent algebras.

ORCID iDs

Chernev, Anton, Cirstea, Corina, Hansen, Helle Hvid and Kupke, Clemens ORCID logoORCID: https://orcid.org/0000-0002-0502-391X;
CORE (COnnecting REpositories)