Skip to main content

Research Repository

Advanced Search

All Outputs (17)

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.

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.

Reachability Problems for Hierarchical Piecewise Constant Derivative Systems (2013)
Conference Proceeding
Bell, P. C., & Chen, S. (2013). Reachability Problems for Hierarchical Piecewise Constant Derivative Systems. In Reachability Problems. RP 2013. Lecture Notes in Computer Science, vol 8169 (46-58). https://doi.org/10.1007/978-3-642-41036-9_6

In this paper, we investigate the computability and complexity of reachability problems for two-dimensional hierarchical piecewise constant derivative (HPCD) systems. The main interest in HPCDs stems from the fact that their reachability problem is o... Read More about Reachability Problems for Hierarchical Piecewise Constant Derivative Systems.

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.

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.