Skip to main content

Research Repository

Advanced Search

All Outputs (19)

The membership problem for subsemigroups of GL2(Z) is NP-complete (2023)
Journal Article
Bell, P. C., Hirvensalo, M., & Potapov, I. (2024). The membership problem for subsemigroups of GL2(Z) is NP-complete. Information and Computation, 296, Article 105132. https://doi.org/10.1016/j.ic.2023.105132

We show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2x2 matrices from the General Linear Group GL(2,Z) is solvable in NP. We extend this to prove that the membership problem is decidable in NP f... Read More about The membership problem for subsemigroups of GL2(Z) is NP-complete.

Decision Questions for Probabilistic Automata on Small Alphabets (2023)
Journal Article
Bell, P. C., & Semukhin, P. (2023). Decision Questions for Probabilistic Automata on Small Alphabets. Logical Methods in Computer Science, 19(4), 1-36. https://doi.org/10.46298/lmcs-19%284%3A36%292023

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... Read More about Decision Questions for Probabilistic Automata on Small Alphabets.

Polynomially ambiguous probabilistic automata on restricted languages (2022)
Journal Article
Bell. (2022). Polynomially ambiguous probabilistic automata on restricted languages. Journal of Computer and System Sciences, 53 - 65. https://doi.org/10.1016/j.jcss.2022.02.002

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 P... Read More about Polynomially ambiguous probabilistic automata on restricted languages.

Towards Uniform Online Spherical Tessellations (2022)
Journal Article
Bell, P., & Potapov, I. (2022). Towards Uniform Online Spherical Tessellations. Discrete and Computational Geometry, 67(4), 1124-1146. https://doi.org/10.1007/s00454-022-00384-x

The problem of uniformly placing 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... Read More about Towards Uniform Online Spherical Tessellations.

On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond (2021)
Journal Article
Bell. (2021). On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond. Information and Computation, https://doi.org/10.1016/j.ic.2021.104736

We consider a variant of the mortality problem: given k × k matrices A1, . . . , At , do there exist nonnegative integers m1, . . . , mt such that Am1 1 · · · Amt t equals the zero matrix? This problem is known to be decidable when t = 2 but undecida... Read More about On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond.

On Injectivity of Quantum Finite Automata (2021)
Journal Article
Bell. (2021). On Injectivity of Quantum Finite Automata. Journal of Computer and System Sciences, 19-33. https://doi.org/10.1016/j.jcss.2021.05.002

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 determining if the acceptance probability function of a MO-QFA is inj... Read More about On Injectivity of Quantum Finite Automata.

Unique decipherability in formal languages (2019)
Journal Article
Bell, P. C., Reidenbach, D., & Shallit, J. O. (2020). Unique decipherability in formal languages. Theoretical Computer Science, 804, 149 - 160. https://doi.org/10.1016/j.tcs.2019.11.022

We consider several language-theoretic aspects of various notions of unique decipherability (or unique factorization) in formal languages. Given a language L at some position within the Chomsky hierarchy, we investigate the language of words UD(L) in... Read More about Unique decipherability in formal languages.

Freeness properties of weighted and probabilistic automata over bounded languages (2019)
Journal Article
Bell, P. C., Chen, S., & Jackson, L. (2019). Freeness properties of weighted and probabilistic automata over bounded languages. Information and Computation, 269, -. https://doi.org/10.1016/j.ic.2019.104440

There has been much research into freeness properties of finitely generated matrix semigroups under various constraints, such as the dimensions of the generator matrices and the semiring over which the matrices are defined. Most freeness problems hav... Read More about Freeness properties of weighted and probabilistic automata over bounded languages.

On the decidability and complexity of problems for restricted hierarchical hybrid systems (2016)
Journal Article
Bell. (2016). On the decidability and complexity of problems for restricted hierarchical hybrid systems. Theoretical Computer Science, 47 - 63. https://doi.org/10.1016/j.tcs.2016.09.003

We study variants of a recently introduced hybrid system model, called a Hierarchical Piecewise Constant Derivative (HPCD). These variants (loosely called Restricted HPCDs) form a class of natural models with similarities to many other well known hyb... Read More about On the decidability and complexity of problems for restricted hierarchical hybrid systems.

Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines (2015)
Journal Article
Bell, P. C., & Wong, P. W. (2015). Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines. Journal of Combinatorial Optimization, 29, 739 - 749. https://doi.org/10.1007/s10878-013-9618-8

In this paper we study energy efficient deadline scheduling on multiprocessors in which the processors consumes power at a rate of sa when running at speed s, where a=2. The problem is to dispatch jobs to processors and determine the speed and jobs t... Read More about Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines.

ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS (2010)
Journal Article
Bell. (2010). ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS. International Journal of Foundations of Computer Science, 963 - 978. https://doi.org/10.1142/S0129054110007660

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 words (over a group alphabet) can generate an identity pair by... Read More about ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS.

The continuous Skolem-Pisot problem (2010)
Journal Article
Bell. (2010). The continuous Skolem-Pisot problem. Theoretical Computer Science, 3625 - 3634. https://doi.org/10.1016/j.tcs.2010.06.005

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. In particular, we show that the continuous version of the nonnegativity... Read More about The continuous Skolem-Pisot problem.

Reachability problems in quaternion matrix and rotation semigroups (2008)
Journal Article
Bell. (2008). Reachability problems in quaternion matrix and rotation semigroups. Information and Computation, 1353 - 1361. https://doi.org/10.1016/j.ic.2008.06.004

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 associative, most of the decision problems for matrix semigroups are undeci... Read More about Reachability problems in quaternion matrix and rotation semigroups.

MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM (2008)
Journal Article
Bell. (2008). MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM. International Journal of Algebra and Computation, 1231 - 1241. https://doi.org/10.1142/S0218196708004925

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 of the equation is undecidable. This is in contrast to the ca... Read More about MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM.

On undecidability bounds for matrix decision problems (2008)
Journal Article
Bell. (2008). On undecidability bounds for matrix decision problems. Theoretical Computer Science, 3 - 13. https://doi.org/10.1016/j.tcs.2007.10.025

In this paper we consider several reachability problems such as vector reachability, membership in matrix semigroups and reachability problems in piecewise linear maps. Since all of these questions are undecidable in general, we work on lowering the... Read More about On undecidability bounds for matrix decision problems.

On the membership of invertible diagonal and scalar matrices (2007)
Journal Article
Bell. (2007). On the membership of invertible diagonal and scalar matrices. Theoretical Computer Science, 37 - 45. https://doi.org/10.1016/j.tcs.2006.11.011

In this paper, we consider decidability questions that are related to the membership problem in matrix semigroups. In particular, we consider the membership of a given invertible diagonal matrix in a matrix semigroup and then a scalar matrix, which h... Read More about On the membership of invertible diagonal and scalar matrices.