Skip to Main content Skip to Navigation
Conference papers

Stream Automata Are Coalgebras

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 papers
Complete list of metadatas

https://hal.inria.fr/hal-01539881
Contributor : Hal Ifip <>
Submitted on : Thursday, June 15, 2017 - 3:02:44 PM
Last modification on : Thursday, June 15, 2017 - 3:25:48 PM
Long-term archiving on: : Wednesday, December 13, 2017 - 11:44:58 AM

File

978-3-642-32784-1_6_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Vincenzo Ciancia, Yde Venema. Stream Automata Are Coalgebras. 11th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Mar 2012, Tallinn, Estonia. pp.90-108, ⟨10.1007/978-3-642-32784-1_6⟩. ⟨hal-01539881⟩

Share

Metrics

Record views

93

Files downloads

148