All Outputs (25)

The membership problem for subsemigroups of GL2(Z) is NP-complete (2023)
Journal Article

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

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

14th and 15th International Conferences on Reachability Problems (2023)
Journal Article

Polynomially ambiguous probabilistic automata on restricted languages (2022)
Journal Article

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

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 Injectivity of Quantum Finite Automata (2021)
Journal Article

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.

On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond (2021)
Journal Article

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.

Unique decipherability in formal languages (2019)
Journal Article

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

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

A Comparison of Distance Metrics in Semi-supervised Hierarchical Clustering Methods (2017)
Book Chapter

On the decidability and complexity of problems for restricted hierarchical hybrid systems (2016)
Journal Article

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

Factorization in Formal Languages (2015)
Book Chapter

Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines (2015)
Journal Article

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

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

ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS (2010)
Journal Article

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

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.