The Expressive Power of Two−Variable Least Fixed−Point Logics
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...
- Host title:
- Symposium on Mathematical Foundations of Computer Science (MFCS)
- Publication date:
- Local pid:
- Deposit date:
- Copyright date:
If you are the owner of this record, you can report an update to it here: Report update to this record