All Outputs (25)

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.

Preface (2023)
Journal Article
Bell, P. C., Potapov, I., Schmitz, S., & Totzke, P. (2023). Preface. Fundamenta Informaticae, 189(3-4), i-iii. https://doi.org/10.3233/fi-222158

14th and 15th International Conferences on Reachability Problems (2023)
Journal Article
Bell, P. C., Potapov, I., Schmitz, S., & Totzke, P. (2023). 14th and 15th International Conferences on Reachability Problems. Fundamenta Informaticae, 189(3-4), i-iii

Polynomially ambiguous probabilistic automata on restricted languages (2022)
Journal Article
Bell, P. (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, P. (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, P. (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.

Towards Uniform Online Spherical Tessellations (2019)
Book Chapter
Bell, P. C., & Potapov, I. (2019). Towards Uniform Online Spherical Tessellations. . Springer International Publishing. https://doi.org/10.1007/978-3-030-22996-2_11

A Comparison of Distance Metrics in Semi-supervised Hierarchical Clustering Methods (2017)
Book Chapter
Aljohani, A., Lai, D. T. C., Bell, P. C., & Edirisinghe, E. A. (2017). A Comparison of Distance Metrics in Semi-supervised Hierarchical Clustering Methods. . Springer International Publishing. https://doi.org/10.1007/978-3-319-63315-2_63

On the decidability and complexity of problems for restricted hierarchical hybrid systems (2016)
Journal Article
Bell, P. (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.

Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages (2016)
Book Chapter
Bell, P. C., Chen, S., & Jackson, L. (2016). Scalar Ambiguity and Freeness in Matrix Semigroups over Bounded Languages. . Springer International Publishing. https://doi.org/10.1007/978-3-319-30000-9_38

Factorization in Formal Languages (2015)
Book Chapter
Bell, P. C., Reidenbach, D., & Shallit, J. (2015). Factorization in Formal Languages. . Springer International Publishing. https://doi.org/10.1007/978-3-319-21500-6_7

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.

Decision Problems for Probabilistic Finite Automata on Bounded Languages (2013)
Journal Article
Bell, P. C., Halava, V., & Hirvensalo, M. (2013). Decision Problems for Probabilistic Finite Automata on Bounded Languages. Fundamenta Informaticae, 123(1), 1-14. https://doi.org/10.3233/fi-2013-797

ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS (2010)
Journal Article
Bell, P. (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, P. (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.