License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.5
URN: urn:nbn:de:0030-drops-95430
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9543/
Go to the corresponding LIPIcs Volume Portal

Hasuo, Ichiro

Coalgebraic Theory of Büchi and Parity Automata: Fixed-Point Specifications, Categorically (Invited Tutorial)

pdf-format:
LIPIcs-CONCUR-2018-5.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{hasuo:LIPIcs:2018:9543,
  author =	{Ichiro Hasuo},
  title =	{{Coalgebraic Theory of B{\"u}chi and Parity Automata: Fixed-Point Specifications, Categorically (Invited Tutorial)}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{5:1--5:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9543},
  URN =		{urn:nbn:de:0030-drops-95430},
  doi =		{10.4230/LIPIcs.CONCUR.2018.5},
  annote =	{Keywords: Coalgebra, category theory, fixed-point logic, automata, B{\"u}chi automata, parity automata}
}

Keywords: Coalgebra, category theory, fixed-point logic, automata, Büchi automata, parity automata
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI