The Expressive Power of Two-Variable Least Fixed-Point Logics

M. Grohe, S. Kreutzer and N. Schweikardt

abstract

The present paper gives a classification of the expressive power of two-variable least fixed-point logics. The main results are:

1. The two-variable fragment of monadic least fixed-point logic with parameters is as expressive as full monadic least fixed-point logic (on binary structures).
2. The two-variable fragment of monadic least fixed-point logic without parameters is as expressive as the two-variable fragment of binary least fixed-point logic without parameters.
3. The two-variable fragment of binary least fixed-point logic with parameters is strictly more expressive than the two-variable fragment of monadic least fixed-point logic with parameters (even on finite strings).

info

links

BibTeX

Link (pdf)

related pages