Narrow Results

It was noticed by Harel in [Har86] that "one can define -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 ω-language is -complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is -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 ω-rational functions realized by finite state Büchi transducers. Indeed Prieur proved in [Pri01, Pri02] that it is decidable whether a given ω-rational function is continuous, while we show here that it is -complete to determine whether a given ω-rational function has at least one point of continuity. Next we prove that it is -complete to determine whether the continuity set of a given ω-rational function is ω-regular. This gives the exact complexity of two problems which were shown to be undecidable in [CFS08].

We prove two new effective properties of rational functions over infinite words which are realized by finite state Büchi transducers. Firstly, for each such function $F:{\mathrm{\Sigma }}^{\omega }\to {\mathrm{\Gamma }}^{\omega }$, one can construct a deterministic Büchi automaton ${𝒜}$ accepting a dense ${\mathrm{\Pi }}_2^0$-subset of ${\mathrm{\Sigma }}^{\omega }$ such that the restriction of $F$ to $L({𝒜})$ is continuous. Secondly, we give a new proof of the decidability of the first Baire class for synchronous $\omega$-rational functions from which we get an extension of this result involving the notion of Wadge classes of regular $\omega$-languages.

We extensively discuss a new interconnection network topology, denoted by ϒ(n,r). Firstly, the ϒ(n,2) network is shown to provide average cost 3 log₂ n while providing superior fault tolerance characteristics. It is defined over any natural number of nodes n using 2n-3 edges for an average degree of 4 and has diameter no greater than k=⌈log₂n⌉ with average diameter as small as . The network is planar and has cyclomatic number n-2. For n=2^t the unbounded maximum degree is 2 log₂ n-1 believed indicative of generally a maximum unbounded degree O(log₂n). The bisection width ranges from 3 when n=2^t to t+1 when n=2^t+1. Secondly, we provide the ϒ*(n,r) network of bounded degree 2r. For n=r^t the ϒ*(n,r) network has asymptotically better average cost than the general deBruijn(r,t) network while also maintaining planarity and cyclomatic property of ϒ(n,2). The ϒ family exhibits unique extremal properties of both theoretical interest and practical importance.