SOME PROBLEMS IN AUTOMATA THEORY WHICH DEPEND ON THE MODELS OF SET THEORY

作者：Finkel Olivier^*

来源：RAIRO - Theoretical Informatics and Applications, 2011, 45(4): 383-397.

DOI：10.1051/ita/2011113

• Automata and formal languages
• logic in computer science
• computational complexity
• infinite words
• omega-languages
• 1-counter automaton
• 2-tape automaton
• cardinality problems
• decision problems
• analytical hierarchy
• largest thin effective coanalytic set
• models of set theory
• independence from the axiomatic system ZFC

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 omega-language L(A) accepted by a Buchi 1-counter automaton A. We prove the following surprising result: there exists a. 1-counter Buchi automaton A such that the cardinality of the complement L(A)(-) of the omega-language L(A) is not determined by ZFC: (1) There is a model VI of ZFC in which L (A)(-) is countable. (2) There is a model V-2 of ZFC in which L (A)(-) has cardinal 2(aleph 0). (3) There is a model V-3 of ZFC in which 1,(A)(-) has cardinal NI with aleph(0) < aleph(1) < 2(aleph 0). We prove a very similar result for the complement of an infinitary rational relation accepted by a 2-tape Buchi automaton B. As a corollary, this proves that the continuum hypothesis may be not satisfied for complements of 1-counter omega-languages and for complements of infinitary rational relations accepted by 2-tape Buchi automata. We infer from the proof of the above results that basic decision problems about 1-counter omega-languages or infinitary rational relations are actually located at the third level of the analytical hierarchy. In particular, the problem to determine whether the complement of a. 1-counter omega-language (respectively, infinitary rational relation) is countable is in Sigma(1)(3)\(Pi(1)(2) boolean OR Sigma(1)(2)). This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

• 出版日期2011-12