Department of Electrical Engineering and Computer Science,
Case Western Reserve University,
Cleveland, OH 44106, USA.;
Accepted: 25 September 2003
The basic framework of domain μ-calculus was formulated in  more than ten years ago. This paper provides an improved formulation of a fragment of the μ-calculus without function space or powerdomain constructions, and studies some open problems related to this μ-calculus such as decidability and expressive power. A class of language equations is introduced for encoding μ-formulas in order to derive results related to decidability and expressive power of non-trivial fragments of the domain μ-calculus. The existence and uniqueness of solutions to this class of language equations constitute an important component of this approach. Our formulation is based on the recent work of Leiss , who established a sophisticated framework for solving language equations using Boolean automata (a.k.a. alternating automata [12,35]) and a generalized notion of language derivatives. Additionally, the early notion of even-linear grammars is adopted here to treat another fragment of the domain μ-calculus.
Mathematics Subject Classification: 03B70 / 68Q45 / 68Q55
Key words: Domain theory / mu-calculus / formal languages / Boolean automata.
© EDP Sciences, 2003