Computer Science – Logic in Computer Science
Scientific paper
2009-10-07
LMCS 5 (4:4) 2009
Computer Science
Logic in Computer Science
Scientific paper
10.2168/LMCS-5(4:4)2009
We prove the following surprising result: there exist a 1-counter B\"uchi automaton and a 2-tape B\"uchi automaton such that the \omega-language of the first and the infinitary rational relation of the second in one model of ZFC are \pi_2^0-sets, while in a different model of ZFC both are analytic but non Borel sets. This shows that the topological complexity of an \omega-language accepted by a 1-counter B\"uchi automaton or of an infinitary rational relation accepted by a 2-tape B\"uchi automaton is not determined by the axiomatic system ZFC. We show that a similar result holds for the class of languages of infinite pictures which are recognized by B\"uchi tiling systems. We infer from the proof of the above results an improvement of the lower bound of some decision problems recently studied by the author.
No associations
LandOfFree
The Complexity of Infinite Computations In Models of Set Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Infinite Computations In Models of Set Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Infinite Computations In Models of Set Theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-36312