License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.25
URN: urn:nbn:de:0030-drops-176771
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17677/
Go to the corresponding LIPIcs Volume Portal

Dong, Ruiwen

Semigroup Intersection Problems in the Heisenberg Groups

pdf-format:
LIPIcs-STACS-2023-25.pdf (0.9 MB)

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

BibTeX - Entry

@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/opus/volltexte/2023/17677},
  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}
}

Keywords: semigroup intersection, orbit intersection, matrix semigroups, Heisenberg group, nilpotent groups
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI