Olivier Finkel - The Complexity of Infinite Computations In Models of Set Theory

lmcs:1205 - Logical Methods in Computer Science, December 21, 2009, Volume 5, Issue 4 - https://doi.org/10.2168/LMCS-5(4:4)2009
The Complexity of Infinite Computations In Models of Set TheoryArticle

Authors: Olivier Finkel

    We prove the following surprising result: there exist a 1-counter Büchi automaton and a 2-tape Büchi 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üchi automaton or of an infinitary rational relation accepted by a 2-tape Büchi 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üchi 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.


    Volume: Volume 5, Issue 4
    Published on: December 21, 2009
    Imported on: January 20, 2009
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Logic,F.1.1,F.1.3,F.4.1,F.4.3

    5 Documents citing this article

    Consultation statistics

    This page has been seen 1613 times.
    This article's PDF has been downloaded 339 times.