Some Problems in Automata Theory Which Depend on the Models of Set Theory

Details Some Problems in Automata Theory Which Depend on the Models of Set Theory Some Problems in Automata Theory Which Depend on the Models of Set Theory

2011-08-14

arxiv.org/abs/1108.2864v1

RAIRO - Theoretical Informatics and Applications 45, 4 (2011) 383 - 397

Computer Science

Formal Languages and Automata Theory

To appear in the journal RAIRO-Theoretical Informatics and Applications

Scientific paper

10.1051/ita/2011113

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 B\"uchi 1-counter automaton $A$. We prove the following surprising result: there exists a 1-counter B\"uchi 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 $V_1$ 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 $L(A)^-$ has cardinal $\aleph_1$ 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 B\"uchi 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 B\"uchi 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_3^1 \setminus (\Pi_2^1 \cup \Sigma_2^1)$. This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

Affiliated with

Also associated with

No associations

Rating

Some Problems in Automata Theory Which Depend on the 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 Some Problems in Automata Theory Which Depend on the Models of Set Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some Problems in Automata Theory Which Depend on the Models of Set Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-712093