English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It was noticed by Harel in [Har86] that "one can define $\Sigma_1^1$-completeversions of the well-known Post Correspondence Problem". We first give acomplete proof of this result, showing that the infinite Post CorrespondenceProblem in a regular $\omega$-language is $\Sigma_1^1$-complete, hence locatedbeyond the arithmetical hierarchy and highly undecidable. We infer from thisresult that it is $\Pi_1^1$-complete to determine whether two given infinitaryrational relations are disjoint. Then we prove that there is an amazing gapbetween two decision problems about $\omega$-rational functions realized byfinite state B\"uchi transducers. Indeed Prieur proved in [Pri01, Pri02] thatit is decidable whether a given $\omega$-rational function is continuous, whilewe 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 provethat it is $\Pi_1^1$-complete to determine whether the continuity set of agiven $\omega$-rational function is $\omega$-regular. This gives the exactcomplexity of two problems which were shown to be undecidable in [CFS08].

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