2026-07-23T21:02:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9543 2024-03-06T10:44:41Z ddc:004 open_access

Coalgebraic Theory of Büchi and Parity Automata: Fixed-Point Specifications, Categorically (Invited Tutorial) Hasuo, Ichiro Coalgebra category theory fixed-point logic automata Büchi automata parity automata Coalgebra is a categorical modeling of state-based dynamics. Final coalgebras - as categorical greatest fixed points - play a central role in the theory; somewhat analogously, most coalgebraic proof techniques have been devoted to greatest fixed-point properties such as safety and bisimilarity. In this tutorial, I introduce our recent coalgebraic framework that accommodates those fixed-point specifications which are not necessarily the greatest. It does so specifically by characterizing the accepted languages of Büchi and parity automata in categorical terms. We present two characterizations of accepted languages. The proof for their coincidence offers a unique categorical perspective of the correspondence between (logical) fixed-point specifications and the (combinatorial) parity acceptance condition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ichiro Hasuo 2018 Is Part Of LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2018.5 urn:nbn:de:0030-drops-95430 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode