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 para...
- Publication date:
- Local pid:
- Copyright date: