The Complexity of Infinite Computations In Models of Set Theory

DOI10.2168/LMCS-5(4:4)2009MaRDI QIDQ3401139zbMATH OpenFDO

Authors Olivier Finkel

Publication date 28 January 2010

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.1268

zbMATH Keywords

1-counter automaton2-tape automaton\(\omega \)-languagesBorel setsCantor topologyeffective coanalytic setindependence from ZFCinfinite wordsmodels of set theorytiling systemstopological complexitytwo-dimensional words

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Consistency and independence results (03E35)

Abstract: 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.

Recommendations

• On computability and tractability for infinite sets
• Infinite time computable model theory
• Complexity of reals in inner models of set theory
• scientific article; zbMATH DE number 5875139
• Set-theoretic models of computations
• Computable classes of constructivizations for models of infinite algorithmic dimension
• Some observations on infinitary complexity
• Infinite computations and the generic finite
• The complexity types of computable sets
• Infinite versions of some problems from finite complexity theory

Cited in

(15)

• Wadge-Wagner hierarchies
• Locally finite -languages and effective analytic sets have the same topological complexity
• Incompleteness theorems, large cardinals, and automata over finite words
• Infinite computations and the generic finite
• Some problems in automata theory which depend on the models of set theory
• Infinite games specified by 2-tape automata
• Incompleteness theorems, large cardinals, and automata over infinite words
• Highly Undecidable Problems For Infinite Computations
• scientific article; zbMATH DE number 1759437 (Why is no real title available?)
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• Polishness of some topologies related to word or tree automata
• Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words
• On the Accepting Power of 2-Tape Büchi Automata
• New Computational Paradigms
• Infinity problems and countability problems for -automata

This page was built for publication: The Complexity of Infinite Computations In Models of Set Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3401139)