Conference item

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

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

Access Document

Files:
• (pdf, 177.6KB)

Authors

Publisher:
Springer
Host title:
Symposium on Mathematical Foundations of Computer Science (MFCS)
Publication date:
2005-01-01
UUID:
Local pid:
cs:1703
Deposit date:
2015-03-31