Coalgebraic automata theory: basic results

Clemens Kupke, Yde Venema

Research output: Contribution to journalArticle

27 Citations (Scopus)

Abstract

We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks. We show that the class of recognizable languages of F-coalgebras is closed under taking unions, intersections, and projections. We also prove that if a nondeterministic F-automaton accepts some coalgebra it accepts a finite one of the size of the automaton. Our main technical result concerns an explicit construction which transforms a given alternating F-automaton into an equivalent nondeterministic one, whose size is exponentially bound by the size of the original automaton.
LanguageEnglish
Article number10
Number of pages43
JournalLogical Methods in Computer Science
Volume4
Issue number4
DOIs
Publication statusPublished - 21 Nov 2008

Fingerprint

Automata theory
Automata Theory
Automata
Coalgebra
Pullback
Functor
Layout
Union
Intersection
Projection
Transform
Closed
Generalise

Keywords

  • automata
  • coalgebraic logics
  • parity games
  • fixed-point logics
  • coalgebraic semantics

Cite this

@article{b70c9b9cee334e30be6606210839910c,
title = "Coalgebraic automata theory: basic results",
abstract = "We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks. We show that the class of recognizable languages of F-coalgebras is closed under taking unions, intersections, and projections. We also prove that if a nondeterministic F-automaton accepts some coalgebra it accepts a finite one of the size of the automaton. Our main technical result concerns an explicit construction which transforms a given alternating F-automaton into an equivalent nondeterministic one, whose size is exponentially bound by the size of the original automaton.",
keywords = "automata, coalgebraic logics , parity games, fixed-point logics, coalgebraic semantics",
author = "Clemens Kupke and Yde Venema",
year = "2008",
month = "11",
day = "21",
doi = "10.2168/LMCS-4(4:10)2008",
language = "English",
volume = "4",
journal = "Logical Methods in Computer Science",
issn = "1860-5974",
number = "4",

}

Coalgebraic automata theory : basic results. / Kupke, Clemens; Venema, Yde .

In: Logical Methods in Computer Science, Vol. 4, No. 4, 10, 21.11.2008.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Coalgebraic automata theory

T2 - Logical Methods in Computer Science

AU - Kupke, Clemens

AU - Venema, Yde

PY - 2008/11/21

Y1 - 2008/11/21

N2 - We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks. We show that the class of recognizable languages of F-coalgebras is closed under taking unions, intersections, and projections. We also prove that if a nondeterministic F-automaton accepts some coalgebra it accepts a finite one of the size of the automaton. Our main technical result concerns an explicit construction which transforms a given alternating F-automaton into an equivalent nondeterministic one, whose size is exponentially bound by the size of the original automaton.

AB - We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks. We show that the class of recognizable languages of F-coalgebras is closed under taking unions, intersections, and projections. We also prove that if a nondeterministic F-automaton accepts some coalgebra it accepts a finite one of the size of the automaton. Our main technical result concerns an explicit construction which transforms a given alternating F-automaton into an equivalent nondeterministic one, whose size is exponentially bound by the size of the original automaton.

KW - automata

KW - coalgebraic logics

KW - parity games

KW - fixed-point logics

KW - coalgebraic semantics

U2 - 10.2168/LMCS-4(4:10)2008

DO - 10.2168/LMCS-4(4:10)2008

M3 - Article

VL - 4

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

SN - 1860-5974

IS - 4

M1 - 10

ER -