Automata for the mu-calculus and Related Results

David Janin, Igor Walukiewicz


The propositional mu-calculus as introduced by Kozen in [4] is
considered. The notion of disjunctive formula is defined and it is shown
that every formula is semantically equivalent to a disjunctive formula.
For these formulas many difficulties encountered in the general case may
be avoided. For instance, satisfiability checking is linear for disjunctive
formulas. This kind of formula gives rise to a new notion of finite automaton
which characterizes the expressive power of the mu-calculus over
all transition systems.

Full Text:


This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library