2026-07-24T06:45:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6186 2024-03-06T10:38:29Z ddc:004 open_access

Coalgebraic Trace Semantics for Buechi and Parity Automata Urabe, Natsuki Shimizu, Shunsuke Hasuo, Ichiro coalgebra Buechi automaton parity automaton probabilistic automaton tree automaton Despite its success in producing numerous general results on state-based dynamics, the theory of coalgebra has struggled to accommodate the Buechi acceptance condition---a basic notion in the theory of automata for infinite words or trees. In this paper we present a clean answer to the question that builds on the "maximality" characterization of infinite traces (by Jacobs and Cirstea): the accepted language of a Buechi automaton is characterized by two commuting diagrams, one for a least homomorphism and the other for a greatest, much like in a system of (least and greatest) fixed-point equations. This characterization works uniformly for the nondeterministic branching and the probabilistic one; and for words and trees alike. We present our results in terms of the parity acceptance condition that generalizes Buechi's. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Natsuki Urabe and Shunsuke Shimizu and Ichiro Hasuo 2016 Is Part Of LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2016.24 urn:nbn:de:0030-drops-61867 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.24 eng https://creativecommons.org/licenses/by/3.0/legalcode