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.
@InProceedings{urabe_et_al:LIPIcs.CONCUR.2016.24, author = {Urabe, Natsuki and Shimizu, Shunsuke and Hasuo, Ichiro}, title = {{Coalgebraic Trace Semantics for Buechi and Parity Automata}}, booktitle = {27th International Conference on Concurrency Theory (CONCUR 2016)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-017-0}, ISSN = {1868-8969}, year = {2016}, volume = {59}, editor = {Desharnais, Jos\'{e}e and Jagadeesan, Radha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.24}, URN = {urn:nbn:de:0030-drops-61867}, doi = {10.4230/LIPIcs.CONCUR.2016.24}, annote = {Keywords: coalgebra, Buechi automaton, parity automaton, probabilistic automaton, tree automaton} }
Feedback for Dagstuhl Publishing