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).
Details
| Book Title |
Symposium on Mathematical Foundations of Computer Science (MFCS) |
| Pages |
422 – 434 |
| Publisher |
Springer |
| Series |
Lecture Notes in Computer Science |
| Year |
2005 |
Links
Related pages
|
People |