Search

We consider a variant of the mortality problem: given k × k matrices A 1 , ... , A t , do there exist nonnegative integers m 1 , ... , m t such that A 1 m 1 ⋯ A t m t equals the zero matrix? This problem is known to be decidable when t ≤ 2 but undecidable for integer matrices with sufficiently large t and k. We prove that for t = 3 this problem is Turing-equivalent to Skolem's problem and thus decidable for k ≤ 3 (resp. k = 4) over (resp. real) algebraic numbers. Consequently, the set of triples (m 1 , m 2 , m 3) for which the equation A 1 m 1 A 2 m 2 A 3 m 3 equals the zero matrix is a finite union of direct products of semilinear sets. For t = 4 we show that the solution set can be non-semilinear, and thus there is unlikely to be a connection to Skolem's problem. We prove decidability for upper-triangular 2 × 2 rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations. [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]

Most computational problems for matrix semigroups and groups are inherently difficult to solve and even undecidable starting from dimension three. The questions about the decidability and complexity of problems for two-dimensional matrix semigroups remain open and are directly linked with other challenging problems in the field. In this paper we study the computational complexity of the problem of determining whether the identity matrix belongs to a matrix semigroup (the Identity Problem) generated by a finite set of 2 × 2 integral unimodular matrices. The Identity Problem for matrix semigroups is a well-known challenging problem, which has remained open in any dimension until recently. It is currently known that the problem is decidable in dimension two and undecidable starting from dimension four. In particular, we show that the Identity Problem for 2 × 2 integral unimodular matrices is NP-hard by a reduction of the Subset Sum Problem and several new encoding techniques. An upper bound for the nontrivial decidability result by C. Choffrut and J. Karhumäki is unknown. However, we derive a lower bound on the minimum length solution to the Identity Problem for a constructible set of instances, which is exponential in the number of matrices of the generator set and the maximal element of the matrices. This shows that the most obvious candidate for an NP algorithm, which is to guess the shortest sequence of matrices which multiply to give the identity matrix, does not work correctly since the certificate would have a length which is exponential in the size of the instance. Both results lead to a number of corollaries confirming the same bounds for vector reachability, scalar reachability and zero in the right upper corner problems. [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]

Abstract: In this paper we consider several reachability problems such as vector reachability, membership in matrix semigroups and reachability problems in piecewise linear maps. Since all of these questions are undecidable in general, we work on lowering the bounds for undecidability. In particular, we show an elementary proof of undecidability of the reachability problem for a set of 5 two-dimensional affine transformations. Then, using a modified version of a standard technique, we also prove that the vector reachability problem is undecidable for two (rational) matrices in dimension 11. The above result can be used to show that the system of piecewise linear functions of dimension 12 with only two intervals has an undecidable set-to-point reachability problem. We also show that the “zero in the upper right corner” problem is undecidable for two integral matrices of dimension 18 lowering the bound from 23. [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]