Document

Track B: Automata, Logic, Semantics, and Theory of Programming

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

We consider semigroup algorithmic problems in the wreath product ℤ ≀ ℤ. Our paper focuses on two decision problems introduced by Choffrut and Karhumäki (2005): the Identity Problem (does a semigroup contain the neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of ℤ ≀ ℤ. We show that both problems are decidable. Our result complements the undecidability of the Semigroup Membership Problem (does a semigroup contain a given element?) in ℤ ≀ ℤ shown by Lohrey, Steinberg and Zetzsche (ICALP 2013), and contributes an important step towards solving semigroup algorithmic problems in general metabelian groups.

Ruiwen Dong. The Identity Problem in ℤ ≀ ℤ Is Decidable. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 124:1-124:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dong:LIPIcs.ICALP.2023.124, author = {Dong, Ruiwen}, title = {{The Identity Problem in \mathbb{Z} ≀ \mathbb{Z} Is Decidable}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {124:1--124:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.124}, URN = {urn:nbn:de:0030-drops-181768}, doi = {10.4230/LIPIcs.ICALP.2023.124}, annote = {Keywords: wreath product, algorithmic group theory, identity problem, polynomial semiring, positive coefficients} }

Document

**Published in:** LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

We consider two algorithmic problems concerning sub-semigroups of Heisenberg groups and, more generally, two-step nilpotent groups. The first problem is Intersection Emptiness, which asks whether a finite number of given finitely generated semigroups have empty intersection. This problem was first studied by Markov in the 1940s. We show that Intersection Emptiness is PTIME decidable in the Heisenberg groups H_n(𝕂) over any algebraic number field 𝕂, as well as in direct products of Heisenberg groups. We also extend our decidability result to arbitrary finitely generated 2-step nilpotent groups.
The second problem is Orbit Intersection, which asks whether the orbits of two matrices under multiplication by two semigroups intersect with each other. This problem was first studied by Babai et al. (1996), who showed its decidability within commutative matrix groups. We show that Orbit Intersection is decidable within the Heisenberg group H₃(ℚ).

Ruiwen Dong. Semigroup Intersection Problems in the Heisenberg Groups. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dong:LIPIcs.STACS.2023.25, author = {Dong, Ruiwen}, title = {{Semigroup Intersection Problems in the Heisenberg Groups}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {25:1--25:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.25}, URN = {urn:nbn:de:0030-drops-176771}, doi = {10.4230/LIPIcs.STACS.2023.25}, annote = {Keywords: semigroup intersection, orbit intersection, matrix semigroups, Heisenberg group, nilpotent groups} }

Document

**Published in:** LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

For a subset B of ℝ, denote by U(B) be the semiring of (univariate) polynomials in ℝ[X] that are strictly positive on B. Let ℕ[X] be the semiring of (univariate) polynomials with non-negative integer coefficients. We study solutions of homogeneous linear equations over the polynomial semirings U(B) and ℕ[X]. In particular, we prove local-global principles for solving single homogeneous linear equations over these semirings. We then show PTIME decidability of determining the existence of non-zero solutions over ℕ[X] of single homogeneous linear equations.
Our study of these polynomial semirings is largely motivated by several semigroup algorithmic problems in the wreath product ℤ≀ℤ. As an application of our results, we show that the Identity Problem (whether a given semigroup contains the neutral element?) and the Group Problem (whether a given semigroup is a group?) for finitely generated sub-semigroups of the wreath product ℤ≀ℤ is decidable when elements of the semigroup generator have the form (y, ±1).

Ruiwen Dong. Solving Homogeneous Linear Equations over Polynomial Semirings. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dong:LIPIcs.STACS.2023.26, author = {Dong, Ruiwen}, title = {{Solving Homogeneous Linear Equations over Polynomial Semirings}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {26:1--26:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.26}, URN = {urn:nbn:de:0030-drops-176784}, doi = {10.4230/LIPIcs.STACS.2023.26}, annote = {Keywords: wreath product, identity problem, polynomial semiring, positive polynomial} }

Document

**Published in:** LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

We show that the Identity Problem is decidable in polynomial time for finitely generated sub-semigroups of the group UT(4, ℤ) of 4 × 4 unitriangular integer matrices. As a byproduct of our proof, we also show the polynomial-time decidability of several subset reachability problems in UT(4, ℤ).

Ruiwen Dong. On the Identity Problem for Unitriangular Matrices of Dimension Four. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dong:LIPIcs.MFCS.2022.43, author = {Dong, Ruiwen}, title = {{On the Identity Problem for Unitriangular Matrices of Dimension Four}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {43:1--43:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.43}, URN = {urn:nbn:de:0030-drops-168415}, doi = {10.4230/LIPIcs.MFCS.2022.43}, annote = {Keywords: identity problem, matrix semigroups, unitriangular matrices} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail