5 citations · 12 across the 10 of their papers we have counts for
11 papers
Factorisability of Low Dimensional Non-Negative Integer Matrices
Paul C. Bell, Eva Foster, Daniel Reidenbach +1
We consider the problem of determining if a given two-dimensional nonnegative integer matrix is the product of two such matrices, excluding trivial units. A matrix with no…
On Word Representations and Embeddings in Complex Matrices
Paul C. Bell, George Kenison, Reino Niskanen +2
Embeddings of word structures into matrix semigroups provide a natural bridge between combinatorics on words and linear algebra. However, low-dimensional matrix semigroups impose s…
On the Identity and Group Problems for Complex Heisenberg Matrices
Paul C. Bell, Reino Niskanen, Igor Potapov +1
We study the Identity Problem, the problem of determining if a finitely generated semigroup of matrices contains the identity matrix; see Problem 3 (Chapter 10.3) in ``Unsolved Pro…
Linear-Time Model Checking Branching Processes
Stefan Kiefer, Pavel Semukhin, Cas Widdershoven
(Multi-type) branching processes are a natural and well-studied model for generating random infinite trees. Branching processes feature both nondeterministic and probabilistic bran…
Decision Questions for Probabilistic Automata on Small Alphabets
Paul C. Bell, Pavel Semukhin
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 degr…
Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs
Paul C. Bell, Pavel Semukhin
We show the surprising result that the cutpoint isolation problem is decidable for Probabilistic Finite Automata (PFA) where input words are taken from a letter-bounded context-fre…
Decidability of membership problems for flat rational subsets of and singular matrices
Volker Diekert, Igor Potapov, Pavel Semukhin
We consider membership problems for rational subsets of the semigroup of matrices over . For a semigroup , the rational subsets are def…
On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond
Paul C. Bell, Igor Potapov, Pavel Semukhin
We consider the following variant of the Mortality Problem: given matrices , does there exist nonnegative integers such tha…
On Reachability Problems for Low-Dimensional Matrix Semigroups
Thomas Colcombet, Joël Ouaknine, Pavel Semukhin +1
We consider the Membership and the Half-Space Reachability problems for matrices in dimensions two and three. Our first main result is that the Membership Problem is decidable for…
Decidability of the Membership Problem for integer matrices
Igor Potapov, Pavel Semukhin
The main result of this paper is the decidability of the membership problem for nonsingular integer matrices. Namely, we will construct the first algorithm that for any…
Vector Reachability Problem in
Igor Potapov, Pavel Semukhin
The decision problems on matrices were intensively studied for many decades as matrix products play an essential role in the representation of various computational processes. Howe…