Some problems in automata theory which depend on the models of set theory
Olivier Finkel · RAIRO - Theoretical Informatics and Applications · 2011
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language accepted by a Büchi 1-counter automaton . We prove the following surprising result: there exists a 1-counter Büchi automaton such that the cardinality of the complement of the ω-language is not determined by ZFC: (1) There is a model V1 of ZFC in which is countable. (2) There is a model V2 of ZFC in which has cardinal 2ℵ0. (3) There is a model V3 of ZFC in which has cardinal ℵ1 with ℵ0 < ℵ1 < 2ℵ0.