Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language

Details Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language

2011-07-29

arxiv.org/abs/1107.5886v1

Computer Science

Logic in Computer Science

To appear in: Special Issue: Frontier Between Decidability and Undecidability and Related Problems, International Journal of F

Scientific paper

It was noticed by Harel in [Har86] that "one can define $\Sigma_1^1$-complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, showing that the infinite Post Correspondence Problem in a regular $\omega$-language is $\Sigma_1^1$-complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is $\Pi_1^1$-complete to determine whether two given infinitary rational relations are disjoint. Then we prove that there is an amazing gap between two decision problems about $\omega$-rational functions realized by finite state B\"uchi transducers. Indeed Prieur proved in [Pri01, Pri02] that it is decidable whether a given $\omega$-rational function is continuous, while we show here that it is $\Sigma_1^1$-complete to determine whether a given $\omega$-rational function has at least one point of continuity. Next we prove that it is $\Pi_1^1$-complete to determine whether the continuity set of a given $\omega$-rational function is $\omega$-regular. This gives the exact complexity of two problems which were shown to be undecidable in [CFS08].

Affiliated with

Also associated with

No associations

Rating

Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language 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 Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-318461