Recent advances in algorithmic problems for semigroups
R Dong - ACM SIGLOG News, 2023 - dl.acm.org
In this article we survey recent progress in the algorithmic theory of matrix semigroups. The
main objective in this area of study is to construct algorithms that decide various properties …
main objective in this area of study is to construct algorithms that decide various properties …
Membership problems in infinite groups
M Lohrey - Conference on Computability in Europe, 2024 - Springer
Membership Problems in Infinite Groups | SpringerLink Skip to main content Advertisement
SpringerLink Account Menu Find a journal Publish with us Track your research Search Cart …
SpringerLink Account Menu Find a journal Publish with us Track your research Search Cart …
Subgroup membership in GL (2, Z)
M Lohrey - Theory of Computing Systems, 2024 - Springer
It is shown that the subgroup membership problem for a virtually free group can be decided
in polynomial time when all group elements are represented by so-called power words, ie …
in polynomial time when all group elements are represented by so-called power words, ie …
The Identity Problem in the special affine group of Z2
R Dong - 2023 38th Annual ACM/IEEE Symposium on Logic in …, 2023 - ieeexplore.ieee.org
We consider semigroup algorithmic problems in the Special Affine group
SA(2,Z)=Z^2SL(2,Z), which is the group of affine transformations of the lattice Z^2 that …
SA(2,Z)=Z^2SL(2,Z), which is the group of affine transformations of the lattice Z^2 that …
Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups
R Dong - Proceedings of the 2025 Annual ACM-SIAM …, 2025 - SIAM
We show that it is undecidable whether a system of linear equations over the Laurent
polynomial ring ℤ [X±] admit solutions where a specified subset of variables take value in …
polynomial ring ℤ [X±] admit solutions where a specified subset of variables take value in …
Decidability of Membership Problems for Flat Rational Subsets of and Singular Matrices
V Diekert, I Potapov, P Semukhin - SIAM Journal on Computing, 2024 - SIAM
We consider membership problems for rational subsets of the semigroup of matrices over.
For a semigroup, the rational subsets are defined as the sets accepted by nondeterministic …
For a semigroup, the rational subsets are defined as the sets accepted by nondeterministic …
Membership problems in braid groups and Artin groups
RD Gray, CF Nyberg-Brodda - arXiv preprint arXiv:2409.11335, 2024 - arxiv.org
We study several natural decision problems in braid groups and Artin groups. We classify
the Artin groups with decidable submonoid membership problem in terms of the non …
the Artin groups with decidable submonoid membership problem in terms of the non …
Submonoid Membership in n-dimensional lamplighter groups and S-unit equations
R Dong - arXiv preprint arXiv:2409.07077, 2024 - arxiv.org
We show that Submonoid Membership is decidable in n-dimensional lamplighter groups
$(\mathbb {Z}/p\mathbb {Z})\wr\mathbb {Z}^ n $ for any prime $ p $ and integer $ n $. More …
$(\mathbb {Z}/p\mathbb {Z})\wr\mathbb {Z}^ n $ for any prime $ p $ and integer $ n $. More …
Solving homogeneous linear equations over polynomial semirings
R Dong - arXiv preprint arXiv:2209.13347, 2022 - arxiv.org
For a subset $ B $ of $\mathbb {R} $, denote by $\operatorname {U}(B) $ be the semiring of
(univariate) polynomials in $\mathbb {R}[X] $ that are strictly positive on $ B $. Let $\mathbb …
(univariate) polynomials in $\mathbb {R}[X] $ that are strictly positive on $ B $. Let $\mathbb …
The word problem and combinatorial methods for groups and semigroups
CF Nyberg Brodda - 2021 - ueaeprints.uea.ac.uk
The subject matter of this thesis is combinatorial semigroup theory. It includes material, in no
particular order, from combinatorial and geometric group theory, formal language theory …
particular order, from combinatorial and geometric group theory, formal language theory …