Stream Automata Are Coalgebras - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

Stream Automata Are Coalgebras

(1) , (1)
1

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.
Fichier principal
Vignette du fichier
978-3-642-32784-1_6_Chapter.pdf (348.24 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01539881 , version 1 (15-06-2017)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

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⟩
43 View
52 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More