4 citations · 11 across the 9 of their papers we have counts for
10 papers
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…
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…
On Injectivity of Quantum Finite Automata
Paul C. Bell, Mika Hirvensalo
We consider notions of freeness and ambiguity for the acceptance probability of Moore-Crutchfield Measure Once Quantum Finite Automata (MO-QFA). We study the injectivity problem of…
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…
Polynomially Ambiguous Probabilistic Automata on Restricted Languages
Paul C. Bell
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 st…
Towards Uniform Online Spherical Tessellations
Paul C. Bell, Igor Potapov
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 o…
Factorization in Formal Languages
Paul Bell, Daniel Reidenbach, Jeffrey Shallit
We consider several novel aspects of unique factorization in formal languages. We reprove the familiar fact that the set uf(L) of words having unique factorization into elements of…
The Identity Correspondence Problem and its Applications
Paul C. Bell, Igor Potapov
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 p…
The Continuous Skolem-Pisot Problem: On the Complexity of Reachability for Linear Ordinary Differential Equations
Paul Bell, Jean-Charles Delvenne, Raphael Jungers +1
We study decidability and complexity questions related to a continuous analogue of the Skolem-Pisot problem concerning the zeros and nonnegativity of a linear recurrent sequence. I…