Stream Automata Are Coalgebras

Authors
Publication date 2012
Host editors
  • D. Pattinson
  • L. Schröder
Book title Coalgebraic Methods in Computer Science
Book subtitle 11th International Workshop, CMCS 2012, colocated with ETAPS 2012, Tallinn, Estonia, March 31 – April 1, 2012 : revised selected papers
ISBN
  • 9783642327834
ISBN (electronic)
  • 9783642327841
Series Lecture Notes in Computer Science
Event Coalgebraic methods in computer science: 11th international workshop, CMCS 2012
Pages (from-to) 90-108
Publisher Heidelberg: Springer
Organisations
  • Faculty of Science (FNWI)
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract Stream automata (also called ω-automata) and ω-regular languages are of paramount importance in Computer Science and Logic. A coalgebraic treatment of these structures has not been given yet. We study a simple two-sorted setting where deterministic Muller automata can be cast as coalgebras, so that coalgebraic bisimilarity coincides with language equivalence. From this characterisation, we derive concise and natural decision procedures for complementation, union, intersection, and equivalence check.
Document type Conference contribution
Language English
Published at https://doi.org/10.1007/978-3-642-32784-1_6
Permalink to this page
Back