On the expressivity of the modal mu-calculus

Julian Bradfield

Abstract: We analyse the complexity of the sets of states, in certain classes of infinite systems, that satisfy formulae of the modal mu-calculus. Improving on some of our earlier results, we establish a strong upper bound (namely Delta12). We also establish various lower bounds and restricted upper bounds, incidentally providing another proof that the mu-calculus alternation hierarchy does not collapse at level 2.

ECS-LFCS-95-338, December 1995.

This report is available in the following formats:

Previous | Index | Next