Anton Chernev ; Corina Cîrstea ; Helle Hvid Hansen ; Clemens Kupke - Unambiguous Acceptance of Thin Coalgebras

entics:16832 - Electronic Notes in Theoretical Informatics and Computer Science, December 20, 2025, Volume 5 - Proceedings of MFPS XLI - https://doi.org/10.46298/entics.16832
Unambiguous Acceptance of Thin CoalgebrasArticle

Authors: Anton Chernev ; Corina Cîrstea ; Helle Hvid Hansen ; Clemens Kupke

    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.


    Volume: Volume 5 - Proceedings of MFPS XLI
    Published on: December 20, 2025
    Accepted on: October 31, 2025
    Submitted on: October 31, 2025
    Keywords: Formal Languages and Automata Theory