# 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:

- 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).
- 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. - 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).

Book Title

Symposium on Mathematical Foundations of Computer Science (MFCS)

Pages

422 – 434

Publisher

Springer

Series

Lecture Notes in Computer Science

Year

2005