Conference item icon

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...
Expand abstract

Actions


Access Document


Files:

Authors


Publisher:
Springer
Host title:
Symposium on Mathematical Foundations of Computer Science (MFCS)
Publication date:
2005-01-01
UUID:
uuid:9bc2cf33-2598-445c-ad0e-816582f4b81a
Local pid:
cs:1703
Deposit date:
2015-03-31

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP