Back to Search
Start Over
Automata and fixed point logic: A coalgebraic perspective
- Source :
-
Information & Computation . Apr2006, Vol. 204 Issue 4, p637-678. 42p. - Publication Year :
- 2006
-
Abstract
- Abstract: This paper generalizes existing connections between automata and logic to a coalgebraic abstraction level. Let F: Set to Set be a standard functor that preserves weak pullbacks. We introduce various notions of F-automata, devices that operate on pointed F-coalgebras. The criterion under which such an automaton accepts or rejects a pointed coalgebra is formulated in terms of an infinite two-player graph game. We also introduce a language of coalgebraic fixed point logic for F-coalgebras, and we provide a game semantics for this language. Finally, we show that the two approaches are equivalent in expressive power. We prove that any coalgebraic fixed point formula can be transformed into an F-automaton that accepts precisely those pointed F-coalgebras in which the formula holds. And conversely, we prove that any F-automaton can be converted into an equivalent fixed point formula that characterizes the pointed F-coalgebras accepted by the automaton. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 204
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 20768249
- Full Text :
- https://doi.org/10.1016/j.ic.2005.06.003