Header menu link for other important links
X
Undecidability of MSO+U
Chandrasekharan Pandu Rangan
Published in Springer Verlag
2016
Volume: 9802 LNCS
   
Pages: 173 - 181
Abstract
As explained in Chap. 9, mso+u logic is an extension of mso that allows to express quantitative properties of structures. One of the consequences of the big expressive power of mso+u is that many decision problems about other quantitative formalisms can be reduced to mso+u. An example is the reduction [CL08] of the non-deterministic index problem to a certain boundedness problem that can be further reduced to mso+u on infinite trees. Therefore, decidability of mso+u would be a very desirable result. © Springer International Publishing Switzerland 2017.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo
Concepts (8)
  •  related image
    Computer science
  •  related image
    Computers
  •  related image
    Boundedness
  •  related image
    Decision problems
  •  related image
    Expressive power
  •  related image
    INFINITE TREES
  •  related image
    Undecidability
  •  related image
    Artificial intelligence