Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecision Problems for Recognizable Languages of Infinite Pictures
181
0
0.0
(
0
)
Added by
Olivier Finkel
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Finkel
Ask ChatGPT about the research
No Arabic abstract
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)$).
rate research
Read More
The theory of finitely supported algebraic structures represents a reformulation of Zermelo-Fraenkel set theory in which every construction is finitely supported according to the action of a group of permutations of some basic elements named atoms. In this paper we study the properties of finitely supported sets that contain infinite uniformly supported subsets, as well as the properties of finitely supported sets that do not contain infinite uniformly supported subsets. For classical atomic sets, we study whether they contain or not infinite uniformly supported subsets.
Algorithmic issues concerning Elliott local semigroups are seldom considered in the literature, although these combinatorial structures completely classify AF algebras. In general, the addition operation of an Elliott local semigroup is {it partial}, but for every AF algebra $mathfrak B$ whose Murray-von Neumann order of projections is a lattice, this operation is uniquely extendible to the addition of an involutive monoid $E(mathfrak B)$. Let $mathfrak M_1$ be the Farey AF algebra introduced by the present author in 1988 and rediscovered by F. Boca in 2008. The freeness properties of the involutive monoid $E(mathfrak M_1)$ yield a natural word problem for every AF algebra $mathfrak B$ with singly generated $E(mathfrak B)$, because $mathfrak B$ is automatically a quotient of $mathfrak M_1$. Given two formulas $phi$ and $psi$ in the language of involutive monoids, the problem asks to decide whether $phi$ and $psi$ code the same equivalence of projections of $mathfrak B$. This mimics the classical definition of the word problem of a group presented by generators and relations. We show that the word problem of $mathfrak M_1$ is solvable in polynomial time, and so is the word problem of the Behnke-Leptin algebras $mathcal A_{n,k}$, and of the Effros-Shen algebras $mathfrak F_{theta}$, for $thetain [0,1]setminus mathbb Q$ a real algebraic number, or $theta = 1/e$. We construct a quotient of $mathfrak M_1$ having a Godel incomplete word problem, and show that no primitive quotient of $mathfrak M_1$ is Godel incomplete.
We study the computational complexity of satisfiability problems for classes of simple finite height (ortho)complemented modular lattices $L$. For single finite $L$, these problems are shown tobe $mc{NP}$-complete; for $L$ of height at least $3$, equivalent to a feasibility problem for the division ring associated with $L$. Moreover, it is shown that the equational theory of the class of subspace ortholattices as well as endomorphism *-rings (with pseudo-inversion) of finite dimensional Hilbert spaces is complete for the complement of the Boolean part of the nondeterministic Blum-Shub-Smale model of real computation without constants. This results extends to the category of finite dimensional Hilbert spaces, enriched by pseudo-inversion.
We consider decision problems for relations over finite and infinite words defined by finite automata. We prove that the equivalence problem for binary deterministic rational relations over infinite words is undecidable in contrast to the case of finite words, where the problem is decidable. Furthermore, we show that it is decidable in doubly exponential time for an automatic relation over infinite words whether it is a recognizable relation. We also revisit this problem in the context of finite words and improve the complexity of the decision procedure to single exponential time. The procedure is based on a polynomial time regularity test for deterministic visibly pushdown automata, which is a result of independent interest.
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
