Let P be the set of prime numbers. We show that for each finite set Π ⊆ P ∖ { 2 } , there exists a subring Λ Π ⊆ Q and an injective polynomial function P : Λ Π × Λ Π → Λ Π .

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.

Abstract We present new results on the computational limitations of affine automata (AfAs). First, we show that using the endmarker does not increase the computational power of AfAs. Second, we show that the computation of bounded-error rational-valued AfAs can be simulated in logarithmic space. Third, we identify some logspace unary languages that are not recognized by algebraic-valued AfAs. Fourth, we show that using arbitrary real-valued transition matrices and state vectors does not increase the computational power of AfAs in the unbounded-error model. When focusing only the rational values, we obtain the same result also for bounded error. As a consequence, we show that the class of bounded-error affine languages remains the same when the AfAs are restricted to use rational numbers only.

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.

Many non-classical models of automata are natural objects of theoretical computer science. They are studied from different points of view in various areas, both as theoretical concepts and as formal models for applications. The Fifth Workshop on Non-Classical Models of Automata and Applications (NCMA 2013) was organized in order to provide an opportunity for researchers who work on different aspects of non-classical models of automata and related subjects to exchange and discuss new ideas and recent developments.

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 give two recursive expressions for both MacWilliams and Chebyshev matrices. The expressions give rise to simple recursive algorithms for constructing the matrices. In order to derive the second recursion for the Chebyshev matrices we find out the

Many non-classical automata models are natural objects of theoretical computer science.They are studied from different points of view in various areas, both as theoretical concepts and as formal models for applications.A deeper and interdisciplinary coverage of this particular area may lead to new insights and substantial progress.The Second Workshop on Non-Classical Models of Automata and Applications (NCMA 2010) has been organized in order to bring together researchers working on different aspects of various variants of non-classical automata models to exchange and develop novel ideas.