Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecision Problems for Subclasses of Rational Relations over Finite and Infinite Words
123
0
0.0
(
0
)
Added by
Christopher Spinrath
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Christof Loding
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
In [1], we introduced the weakly synchronizing languages for probabilistic automata. In this report, we show that the emptiness problem of weakly synchronizing languages for probabilistic automata is undecidable. This implies that the decidability result of [1-3] for the emptiness problem of weakly synchronizing language is incorrect.
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)$).
The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability, and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability $epsilonleq 1/3$ by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error probability $epsilonleq 1/3$; and especially, (3) there are promise problems $A(p)$ with prime $p$ that can be solved {em with any error probability} by MO-1QFA with only two quantum basis states, but they can not be solved exactly by any MO-1QFA with two quantum basis states; in contrast, the minimal PFA solving $A(p)$ with any error probability (usually smaller than $1/2$) has $p$ states. Finally, we mention a number of problems related to promise for further study.
If the $ell$-adic cohomology of a projective smooth variety, defined over a local field $K$ with finite residue field $k$, is supported in codimension $ge 1$, then every model over the ring of integers of $K$ has a $k$-rational point. For $K$ a $p$-adic field, this is math/0405318, Theorem 1.1. If the model $sX$ is regular, one has a congruence $|sX(k)|equiv 1 $ modulo $|k|$ for the number of $k$-rational points 0704.1273, Theorem 1.1. The congruence is violated if one drops the regularity assumption.
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X subseteq F^*$. We say that a submonoid $M$ generated by $k$ elements of $A^*$ is {em $k$-maximal} if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X subseteq A^*$ {em primitive} if it is the basis of a $|X|$-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, ${w}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X subseteq Y^*$. We therefore call $Y$ a {em primitive root} of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. To obtain this result, we prove that the intersection of two $2$-maximal submonoids is either the empty word or a submonoid generated by one single primitive word. For a single word $w$, we say that the set ${x,y}$ is a {em bi-root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and ${x,y}$ is a primitive set. We prove that every primitive word $w$ has at most one bi-root ${x,y}$ such that $|x|+|y|<sqrt{|w|}$. That is, the bi-root of a word is unique provided the word is sufficiently long with respect to the size (sum of lengths) of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $theta$ is defined on $A^*$. In this setting, the notions of $theta$-power, $theta$-primitive and $theta$-root are defined, and it is shown that any word has a unique $theta$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $theta$-primitive if and only if ${w, theta(w)}$ is a primitive set.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
