Alternating Context-Free Languages and Linear Time μ-Calculus with Sequential Composition
Martin Lange · Electronic Notes in Theoretical Computer Science · 2002
This paper shows that linear time μ-calculus with sequential composition defines exactly those properties that are expressible with alternating context-free grammars for ω-words. This helps to understand the expressive power of modal μ-calculus with a chop operator and provides a logical characterisation of the class of alternating context-free languages.