Abstract | ||
---|---|---|
Despite its success in producing numerous general results on state-based dynamics, theory of coalgebra has struggled to accommodate 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 question that builds on maximality characterization of infinite traces (by Jacobs and Cirstea): accepted language of a Buechi automaton is characterized by two commuting diagrams, one for a least homomorphism and other for a greatest, much like in a system of (least and greatest) fixed-point equations. This characterization works uniformly for nondeterministic branching and probabilistic one; and for words and trees alike. We present our results in terms of parity acceptance condition that generalizes Buechiu0027s. |
Year | DOI | Venue |
---|---|---|
2016 | 10.4230/LIPIcs.CONCUR.2016.24 | international conference on concurrency theory |
DocType | Volume | Citations |
Conference | abs/1606.09399 | 2 |
PageRank | References | Authors |
0.39 | 1 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Natsuki Urabe | 1 | 14 | 4.69 |
Shunsuke Shimizu | 2 | 5 | 1.12 |
Ichiro Hasuo | 3 | 260 | 26.13 |