Header menu link for other important links
X
Conclusions
Chandrasekharan Pandu Rangan
Published in Springer Verlag
2016
Volume: 9802 LNCS
   
Pages: 205 - 206
Abstract
The results of the thesis involve a number of methods of descriptive set theory. One of themost common examples is topological hardness: sometimes it is enough to find topologically hard language to obtain some negative results of non-definability. An instance of this approach areChaps. 9 and 10 where negative results about decidability of MSO+U are given. First, in Chap. 9 examples of MSO+U-definable languages lying arbitrarily high in the projective hierarchy are given. In consequence there can be no simple automata model capturing MSO+U on ω-words. The topological hardness of MSO+U is later used in Chap. 10 to prove that the MSO+U theory of the complete binary tree cannot be decidable in the standard sense. Also, topological hardness is used in Chap. 5 to prove that index bounds computed by the proposed algorithm (see Sect. 5.4.1, page 79) are tight.Additionally, the dichotomy proved in Chap. 6 involves topological hardness: a regular language of thin trees is either wmso-definable or ∏1/1-hard. © Springer International Publishing Switzerland 2016.
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 (11)
  •  related image
    Binary trees
  •  related image
    Computability and decidability
  •  related image
    Hardness
  •  related image
    Set theory
  •  related image
    AUTOMATA MODELS
  •  related image
    COMPLETE BINARY TREE
  •  related image
    DEFINABILITY
  •  related image
    DESCRIPTIVE SET THEORY
  •  related image
    HARD LANGUAGES
  •  related image
    NUMBER OF METHODS
  •  related image
    Topology