Search

We consider the computability and complexity of decision questions for Probabilistic Finite Automata (PFA) with sub-exponential ambiguity. We show that the emptiness problem for strict and non-strict cut-points of polynomially ambiguous commutative PFA remains undecidable, implying that the problem is undecidable when inputs are from a letter monotonic language. We show that the problem remains undecidable over a binary input alphabet when the input word is over a bounded language, in the noncommutative case. In doing so, we introduce a new technique based upon the Turakainen construction of a PFA from a Weighted Finite Automaton which can be used to generate PFA of lower dimensions and of sub-exponential ambiguity. We also study freeness/injectivity problems for polynomially ambiguous PFA and study the border of decidability and tractability for various cases. [ABSTRACT FROM AUTHOR]

We consider notions of freeness and ambiguity for the acceptance probability of Moore-Crutchfield Measure Once Quantum Finite Automata (MO-QFA). We study the injectivity problem of determining if the acceptance probability function of a MO-QFA is injective over all input words, i.e., giving a distinct probability for each input word. We show that the injectivity problem is undecidable for 8 state MO-QFA, even when all unitary matrices and the projection matrix are rational and the initial state vector is real algebraic. We also show undecidability of this problem when the initial vector is rational, although with a huge increase in the number of states. We utilize properties of quaternions, free rotation groups, representations of tuples of rationals as linear sums of radicals and a reduction of the mixed modification of Post's correspondence problem, as well as a new result on rational polynomial packing functions which may be of independent interest. [ABSTRACT FROM AUTHOR]

We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert's tenth problem. We then consider the set of so called 'F-Problems' (emptiness, infiniteness, containment, disjointness, universe and equivalence) and show that they are also undecidable for bounded (non-)strict cut-point languages on probabilistic finite automata. For a finite set of matrices $\{M_1, M_2, \ldots ,M_k\} \subseteq \mathbb{Q}^{t \times t}$, we then consider the decidability of computing the maximal spectral radius of any matrix in the set $X = \{M^{j_1}_1 M^{j_2}_2 \cdot M^{j_k}_k \vert j_1, j_2,\ldots, j_k \geq 0\}$, which we call a bounded matrix language. Using an encoding of a probabilistic finite automaton shown in the paper, we prove the surprising result that determining if the maximal spectral radius of a bounded matrix language is less than or equal to one is undecidable, but determining whether it is strictly less than one is in fact decidable (which is similar to a result recently shown for quantum automata). [ABSTRACT FROM AUTHOR]

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. In the second part of the paper we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup S of integral square matrices whether or not the identity matrix belongs to S?". We show that the problem is undecidable starting from dimension four even when the number of matrices in the generator is 48. From this fact, we can immediately derive that the fundamental problem of whether a finite set of matrices generates a group is also undecidable. We also answer several questions for matrices over different number fields. Apart from the application to matrix problems, we believe that the Identity Correspondence Problem will also be useful in identifying new areas of undecidable problems in abstract algebra, computational questions in logic and combinatorics on words. [ABSTRACT FROM AUTHOR]

We show a reduction of Hilbert's tenth problem to the solvability of the matrix equation $X_1^{i_1}X_2^{i_2}\cdots X_k^{i_k} = Z$ over non-commuting integral matrices, where Z is the zero matrix, thus proving that the solvability of the equation is undecidable. This is in contrast to the case whereby the matrix semigroup is commutative in which the solvability of the same equation was shown to be decidable in general. The restricted problem where k = 2 for commutative matrices is known as the "A-B-C Problem" and we show that this problem is decidable even for a pair of non-commutative matrices over an algebraic number field. [ABSTRACT FROM AUTHOR]

Abstract: We examine computational problems on quaternion matrix and rotation semigroups. It is shown that in the ultimate case of quaternion matrices, in which multiplication is still associative, most of the decision problems for matrix semigroups are undecidable in dimension two. The geometric interpretation of matrix problems over quaternions is presented in terms of rotation problems for the 2- and 3-sphere. In particular, we show that the reachability of the rotation problem is undecidable on the 3-sphere and other rotation problems can be formulated as matrix problems over complex and hypercomplex numbers. [Copyright &y& Elsevier]

We consider decidability questions for the emptiness problem of intersections of matrix semigroups. This problem was studied by A. Markov [7] and more recently by V. Halava and T. Harju [5]. We give slightly strengthened results of their theorems by using a different matrix encoding. In particular, we show that given two finitely generated semigroups of non-singular upper triangular 3 × 3 matrices over the natural numbers, checking the emptiness of their intersections is undecidable. We also show that the problem is undecidable even for unimodular matrices over 3 × 3 rational matrices. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider decidability questions that are related to the membership problem in matrix semigroups. In particular, we consider the membership of a given invertible diagonal matrix in a matrix semigroup and then a scalar matrix, which has a separate geometric interpretation. Both problems have been open for any dimensions and are shown to be undecidable in dimension 4 with integral matrices by a reduction of the Post Correspondence Problem (PCP). Although the idea of PCP reduction is standard for such problems, we suggest a new coding technique to cover the case of diagonal matrices. [Copyright &y& Elsevier]

There has been much research into freeness properties of finitely generated matrix semigroups under various constraints. Most freeness problems are undecidable starting from dimension three, even for upper-triangular integer matrices. A recent paper investigated freeness properties of bounded languages of matrices, which are matrices from a set M 1 ⁎ M 2 ⁎ ⋯ M k ⁎ ⊆ F n × n for some semiring F and fixed k ∈ N > 0. We consider a notion of freeness and ambiguity for scalar reachability problems in matrix semigroups and bounded languages of matrices. Scalar reachability concerns the set { ρ T M τ | M ∈ S } , where ρ , τ ∈ F n are vectors and S ⊆ F n × n is a finitely generated matrix semigroup. Ambiguity and freeness problems are defined in terms of the uniqueness of factorizations for each scalar. We show various undecidability results and connections to weighted and probabilistic finite automata. [ABSTRACT FROM AUTHOR]