Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Upper Bound on the Complexity of Recognizable Tree Languages
193
0
0.0
(
0
)
Added by
Dominique Lecomte
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Finkel
Ask ChatGPT about the research
No Arabic abstract
The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $Game (D_n({bfSigma}^0_2))$ for some natural number $ngeq 1$, where $Game$ is the game quantifier. We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space $2^omega$ into the class ${bfDelta}^1_2$, and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ${bfDelta}^1_2$.
rate research
Read More
In arXiv:1711.10132 a new approximating invariant ${mathsf{TC}}^{mathcal{D}}$ for topological complexity was introduced called $mathcal{D}$-topological complexity. In this paper, we explore more fully the properties of ${mathsf{TC}}^{mathcal{D}}$ and the connections between ${mathsf{TC}}^{mathcal{D}}$ and invariants of Lusternik-Schnirelmann type. We also introduce a new $mathsf{TC}$-type invariant $widetilde{mathsf{TC}}$ that can be used to give an upper bound for $mathsf{TC}$, $$mathsf{TC}(X)le {mathsf{TC}}^{mathcal{D}}(X) + leftlceil frac{2dim X -k}{k+1}rightrceil,$$ where $X$ is a finite dimensional simplicial complex with $k$-connected universal cover $tilde X$. The above inequality is a refinement of an estimate given by Dranishnikov.
We survey recent results on the topological complexity of context-free omega-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In particular, we consider the Borel hierarchy and the Wadge hierarchy of non-deterministic or deterministic context-free omega-languages. We study also decision problems, the links with the notions of ambiguity and of degrees of ambiguity, and the special case of omega-powers.
Altenbernd, Thomas and Wohrle have considered in [ATW02] acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acceptance conditions, such as the Buchi and Muller ones, firstly used for infinite words. Many classical decision problems are studied in formal language theory and in automata theory and arise now naturally about recognizable languages of infinite pictures. We first review in this paper some recent results of [Fin09b] where we gave the exact degree of numerous undecidable problems for Buchi-recognizable languages of infinite pictures, which are actually located at the first or at the second level of the analytical hierarchy, and highly undecidable. Then we prove here some more (high) undecidability results. We first show that it is $Pi_2^1$-complete to determine whether a given Buchi-recognizable languages of infinite pictures is unambiguous. Then we investigate cardinality problems. Using recent results of [FL09], we prove that it is $D_2(Sigma_1^1)$-complete to determine whether a given Buchi-recognizable language of infinite pictures is countably infinite, and that it is $Sigma_1^1$-complete to determine whether a given Buchi-recognizable language of infinite pictures is uncountable. Next we consider complements of recognizable languages of infinite pictures. Using some results of Set Theory, we show that the cardinality of the complement of a Buchi-recognizable language of infinite pictures may depend on the model of the axiomatic system ZFC. We prove that the problem to determine whether the complement of a given Buchi-recognizable language of infinite pictures is countable (respectively, uncountable) is in the class $Sigma_3^1 setminus (Pi_2^1 cup Sigma_2^1)$ (respectively, in the class $Pi_3^1 setminus (Pi_2^1 cup Sigma_2^1)$).
Let ${bf P}_k^{(alpha, beta)} (x)$ be an orthonormal Jacobi polynomial of degree $k.$ We will establish the following inequality begin{equation*} max_{x in [delta_{-1},delta_1]}sqrt{(x- delta_{-1})(delta_1-x)} (1-x)^{alpha}(1+x)^{beta} ({bf P}_{k}^{(alpha, beta)} (x))^2 < frac{3 sqrt{5}}{5}, end{equation*} where $delta_{-1}<delta_1$ are appropriate approximations to the extreme zeros of ${bf P}_k^{(alpha, beta)} (x) .$ As a corollary we confirm, even in a stronger form, T. Erd{e}lyi, A.P. Magnus and P. Nevai conjecture [Erd{e}lyi et al., Generalized Jacobi weights, Christoffel functions, and Jacobi polynomials, SIAM J. Math. Anal. 25 (1994), 602-614], by proving that begin{equation*} max_{x in [-1,1]}(1-x)^{alpha+{1/2}}(1+x)^{beta+{1/2}}({bf P}_k^{(alpha, beta)} (x))^2 < 3 alpha^{1/3} (1+ frac{alpha}{k})^{1/6}, end{equation*} in the region $k ge 6, alpha, beta ge frac{1+ sqrt{2}}{4}.$
A language over an alphabet $B = A cup overline{A}$ of opening ($A$) and closing ($overline{A}$) brackets, is balanced if it is a subset of the Dyck language $D_B$ over $B$, and it is well-formed if all words are prefixes of words in $D_B$. We show that well-formedness of a context-free language is decidable in polynomial time, and that the longest common reduced suffix can be computed in polynomial time. With this at a hand we decide for the class 2-TWs of non-linear tree transducers with output alphabet $B^*$ whether or not the output language is balanced.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
