expressibility of mu-calculus

(not really databases, but this seems to be the community with the highest level of expertise on expressibility...)

I'm wondering what is known about the expressive power of regular expressions versus the mu-calculus. This arises from my reading on two approaches to specialized uses of data flow analysis: one [Olender & Osterwiel IEEE TSE 1990] in which event sequences of interest are specified using regular expressions and the other [Steffen, Science of Computer Programming 1993] in which various data flow properties (live vars, available exps, etc.) are expressed as formulae in the modal mu-calculus.

Intuition says that I can specify more things in the mu-calculus, particularly since it is know to capture the bisimulation-invariant fragment of monadic second-order logic (for example, [Rohde ALIG 2002]).

I'd appreciate any suitable references to the literature. Abiteboul's DB theory textbook doesn't seem to have anything.

Thanks,
John

• Phd. Student, CIS Dept., University of Oregon
• Deschutes 234 x6-1385
• http://www.cs.uoregon.edu/~johnfl johnfl_at_cs.uoregon.edu

  ---

  Not in our name will you wage endless war there can be no more deaths http://www.notinourname.net/ no more transfusions of blood for oil

  ---