Search Results

Documents authored by Dong, Ruiwen

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.124
The Identity Problem in ℤ ≀ ℤ Is Decidable

Authors: Ruiwen Dong

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

Abstract
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.
Cite as

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.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
DOI: 10.4230/LIPIcs.STACS.2023.25
Semigroup Intersection Problems in the Heisenberg Groups

Authors: Ruiwen Dong

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

Abstract
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₃(ℚ).
Cite as

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.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
DOI: 10.4230/LIPIcs.STACS.2023.26
Solving Homogeneous Linear Equations over Polynomial Semirings

Authors: Ruiwen Dong

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

Abstract
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).
Cite as

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.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
DOI: 10.4230/LIPIcs.MFCS.2022.43
On the Identity Problem for Unitriangular Matrices of Dimension Four

Authors: Ruiwen Dong

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

Abstract
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, ℤ).
Cite as

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.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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact