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 …

There are several known undecidable problems for 3× 3 integer matrices the proof of which
use a reduction from the Post Correspondence Problem (PCP). We establish new lower …

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 …

Unlike factorization theory of commutative semigroups which are well-studied, very little
literature exists describing factorization properties in noncommutative semigroups. Perhaps …

We show a reduction of Hilbert's tenth problem to the solvability of the matrix equation over
non-commuting integral matrices, where Z is the zero matrix, thus proving that the solvability …

We consider two algorithmic problems concerning subsemigroups of Heisenberg groups
and, more generally, 2-step nilpotent groups. The first problem is Intersection Emptiness …

We construct a probabilistic finite automaton (PFA) with 7 states and an input alphabet of 5
symbols for which the PFA Emptiness Problem is undecidable. The only input for the …

We first investigate factorizations of elements of the semigroup S of upper triangular matrices
with nonnegative entries and nonzero determinant, provide a formula for ϱ (S), and, given …

This is a survey on some undecidable problems on integer matrices. The proofs of these
results employ special instances, called Claus instances, of the Post Correspondence …

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 …