We show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2×2 matrices from the modular group PSL2(Z), the Special Linear group SL2(Z) and the General Linear Group GL2(Z) is solvable in NP. We extend this to prove that the membership problem is decidable in NP for GL2(Z) and for any arbitrary regular expression over matrices from SL2(Z). We then derive that the problems of whether a given finite set of matrices from SL2(Z) or PSL2(Z) generates a group or a free semigroup are both decidable in NP. The previous algorithm for these problems, shown in 2005 by Choffrut and Karhumäki, was in EXPSPACE. Our algorithm is based on new techniques allowing us to operate on compressed word representations of matrices without explicit expansions. When combined with the known NP-hard lower bound, this proves that the identity (and thus membership) problem over GL2(Z) is NP-complete, and the group problem and the non-freeness problem in SL2(Z) are NP-complete. Thus the paper answer the long standing open question on the complexity of the membership problem in semigroups generated by matrices from GL2(Z). We develop novel techniques that can be used for solving numerical matrix problems in symbolic form, which are applicable for solving compressed word problems for groups and semigroups, bridging the gap between combinatorial group theory, computational problems on matrices and complexity theory.

We study the emptiness and $\lambda$-reachability problems for unary and binary Probabilistic Finite Automata (PFA) and characterise the complexity of these problems in terms of the degree of ambiguity of the automaton and the size of its alphabet. Our main result is that emptiness and $\lambda$-reachability are solvable in EXPTIME for polynomially ambiguous unary PFA and if, in addition, the transition matrix is binary, we show they are in NP. In contrast to the Skolem-hardness of the $\lambda$-reachability and emptiness problems for exponentially ambiguous unary PFA, we show that these problems are NP-hard even for finitely ambiguous unary PFA. For binary polynomially ambiguous PFA with fixed and commuting transition matrices, we prove NP-hardness of the $\lambda$-reachability (dimension 9), nonstrict emptiness (dimension 37) and strict emptiness (dimension 40) problems.

Abstract The problem of uniformly placing N points onto a sphere finds applications in many areas. For example, points on the sphere correspond to unit quaternions as well as to the group of rotations SO(3) and the online version of generating uniform rotations (known as “incremental generation”) plays a crucial role in a large number of engineering applications ranging from robotics and aeronautics to computer graphics. An online version of this problem was recently studied with respect to the gap ratio as a measure of uniformity. The first online algorithm of Chen et al. was upper-bounded by 5.99 and later improved to 3.69, which is achieved by considering a circumscribed dodecahedron followed by a recursive decomposition of each face. In this paper we provide a more efficient tessellation technique based on the regular icosahedron, which improves the upper-bound for the online version of this problem, decreasing it to approximately 2.84. Moreover, we show that the lower bound for the gap ratio of placing at least three points is $$({1+\sqrt{5}})/2\approx 1.618$$ ( 1 + 5 ) / 2 ≈ 1.618 and for at least four points is no less than 1.726.

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.

We study the emptiness and λ-reachability problems for unary and binary Probabilistic Finite Automata (PFA) and characterise the complexity of these problems in terms of the degree of ambiguity of the automaton and the size of its alphabet. Our main result is that emptiness and λ-reachability are solvable in EXPTIME for polynomially ambiguous unary PFA and if, in addition, the transition matrix is over {0, 1}, we show they are in NP. In contrast to the Skolem-hardness of the λ-reachability and emptiness problems for exponentially ambiguous unary PFA, we show that these problems are NP-hard even for finitely ambiguous unary PFA. For binary polynomially ambiguous PFA with commuting transition matrices, we prove NP-hardness of the λ-reachability (dimension 9), nonstrict emptiness (dimension 37) and strict emptiness (dimension 40) problems.

We consider the following variant of the Mortality Problem: given $k\times k$ matrices $A_1, A_2, \dots,A_{t}$, does there exist nonnegative integers $m_1, m_2, \dots,m_t$ such that the product $A_1^{m_1} A_2^{m_2} \cdots A_{t}^{m_{t}}$ is equal to the zero matrix? It is known that this problem is decidable when $t \leq 2$ for matrices over algebraic numbers but becomes undecidable for sufficiently large $t$ and $k$ even for integral matrices. In this paper, we prove the first decidability results for $t>2$. We show as one of our central results that for $t=3$ this problem in any dimension is Turing equivalent to the well-known Skolem problem for linear recurrence sequences. Our proof relies on the Primary Decomposition Theorem for matrices that was not used to show decidability results in matrix semigroups before. As a corollary we obtain that the above problem is decidable for $t=3$ and $k \leq 3$ for matrices over algebraic numbers and for $t=3$ and $k=4$ for matrices over real algebraic numbers. Another consequence is that 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 equal to a finite union of direct products of semilinear sets. For $t=4$ we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem is still decidable for upper-triangular $2 \times 2$ rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.

We show the surprising result that the cutpoint isolation problem is decidable for probabilistic finite automata where input words are taken from a letter-bounded context-free language. A context-free language ℒ is letter-bounded when ℒ ⊆ a₁^* a₂^* ⋯ a_𝓁^* for some finite 𝓁 > 0 where each letter is distinct. A cutpoint is isolated when it cannot be approached arbitrarily closely. The decidability of this problem is in marked contrast to the situation for the (strict) emptiness problem for PFA which is undecidable under the even more severe restrictions of PFA with polynomial ambiguity, commutative matrices and input over a letter-bounded language as well as to the injectivity problem which is undecidable for PFA over letter-bounded languages. We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous. We also show that the problem is at least NP-hard and use our decision procedure to solve several related problems.

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 non-strict cut-points of polynomially ambiguous PFA remains undecidable even when the input word is over a bounded language and all PFA transition matrices are commutative. In doing so, we introduce a new technique based upon the Turakainen construction of a PFA from a Weighted Finite Automata which can be used to generate PFA of lower dimensions and of subexponential ambiguity. We also study freeness/injectivity problems for polynomially ambiguous PFA and study the border of decidability and tractability for various cases.

We consider notions of freeness and ambiguity for the acceptance probability of Moore-Crutchfield Measure Once Quantum Finite Automata (MO-QFA). We study the distribution of acceptance probabilities of such MO-QFA, which is partly motivated by similar freeness problems for matrix semigroups and other computational models. We show that determining if the acceptance probabilities of all possible input words are unique is undecidable for 32 state MO-QFA, even when all unitary matrices and the projection matrix are rational and the initial configuration is defined over real algebraic numbers. We utilize properties of the skew field of quaternions, free rotation groups, representations of tuples of rationals as a linear sum of radicals and a reduction of the mixed modification Post’s correspondence problem.

In this paper, we show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2 × 2 matrices from the modular group PSL2(ℤ) and thus the Special Linear group SL2(ℤ) is solvable in NP. From this fact, we can immediately derive that the fundamental problem of whether a given finite set of matrices from SL2(ℤ) or PSL2(ℤ) generates a group or free semigroup is also decidable in NP. The previous algorithm for these problems, shown in 2005 by Choffrut and Karhumaki, was in EXPSPACE mainly due to the translation of matrices into exponentially long words over a binary alphabet {s, r} and further constructions with a large nondeterministic finite state automaton that is built on these words. Our algorithm is based on various new techniques that allow us to operate with compressed word representations of matrices without explicit expansions. When combined with the known NP-hard lower bound, this proves that the membership problem for the identity problem, the group problem and the freeness problem in SL2 (ℤ) are NP-complete.

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.

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 r