All Outputs (4)

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.

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

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