Search Results

Documents authored by Elder, Murray

Document
DOI: 10.4230/LIPIcs.STACS.2022.26
The Isomorphism Problem for Plain Groups Is in Σ₃^{𝖯}

Authors: Heiko Dietrich, Murray Elder, Adam Piggott, Youming Qiao, and Armin Weiß

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. Sénizergues and the fifth author (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable in PSPACE when the input is given in terms of so-called virtually free presentations. Here we consider the isomorphism problem for the class of plain groups, that is, groups that are isomorphic to a free product of finitely many finite groups and finitely many copies of the infinite cyclic group. Every plain group is naturally and efficiently presented via an inverse-closed finite convergent length-reducing rewriting system. We prove that the isomorphism problem for plain groups given in this form lies in the polynomial time hierarchy, more precisely, in Σ₃^𝖯. This result is achieved by combining new geometric and algebraic characterisations of groups presented by inverse-closed finite convergent length-reducing rewriting systems developed in recent work of the second and third authors (2021) with classical finite group isomorphism results of Babai and Szemerédi (1984).
Cite as

Heiko Dietrich, Murray Elder, Adam Piggott, Youming Qiao, and Armin Weiß. The Isomorphism Problem for Plain Groups Is in Σ₃^{𝖯}. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dietrich_et_al:LIPIcs.STACS.2022.26,
  author =	{Dietrich, Heiko and Elder, Murray and Piggott, Adam and Qiao, Youming and Wei{\ss}, Armin},
  title =	{{The Isomorphism Problem for Plain Groups Is in \Sigma₃^\{𝖯\}}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.26},
  URN =		{urn:nbn:de:0030-drops-158368},
  doi =		{10.4230/LIPIcs.STACS.2022.26},
  annote =	{Keywords: plain group, isomorphism problem, polynomial hierarchy, \Sigma₃^\{𝖯\} complexity class, inverse-closed finite convergent length-reducing rewriting system}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.110
Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Laura Ciobanu and Murray Elder

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, with or without torsion, as shortlex geodesic words, is an EDT0L language whose specification can be computed in NSPACE(n^2 log n) for the torsion-free case and NSPACE(n^4 log n) for the torsion case. Our work combines deep geometric results by Rips, Sela, Dahmani and Guirardel on decidability of existential theories of hyperbolic groups, work of computer scientists including Plandowski, Jeż, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and an intricate language-theoretic analysis. The present work gives an essentially optimal formal language description for all solutions in all hyperbolic groups, and an explicit and surprising low space complexity to compute them.
Cite as

Laura Ciobanu and Murray Elder. Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 110:1-110:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ciobanu_et_al:LIPIcs.ICALP.2019.110,
  author =	{Ciobanu, Laura and Elder, Murray},
  title =	{{Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{110:1--110:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.110},
  URN =		{urn:nbn:de:0030-drops-106867},
  doi =		{10.4230/LIPIcs.ICALP.2019.110},
  annote =	{Keywords: Hyperbolic group, Existential theory, EDT0L language, PSPACE}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.96
Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups

Authors: Volker Diekert and Murray Elder

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We prove that the full solution set of a twisted word equation with regular constraints is an EDT0L language. It follows that the set of solutions to equations with rational constraints in a context-free group (= finitely generated virtually free group) in reduced normal forms is EDT0L. We can also decide whether or not the solution set is finite, which was an open problem. Moreover, this can all be done in PSPACE. Our results generalize the work by Lohrey and Senizergues (ICALP 2006) and Dahmani and Guirardel (J. of Topology 2010) with respect to complexity and with respect to expressive power. Both papers show that satisfiability is decidable, but neither gave any concrete complexity bound. Our results concern all solutions, and give, in some sense, the "optimal" formal language characterization.
Cite as

Volker Diekert and Murray Elder. Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 96:1-96:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.ICALP.2017.96,
  author =	{Diekert, Volker and Elder, Murray},
  title =	{{Solutions of Twisted Word Equations, EDT0L Languages, and Context-Free Groups}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{96:1--96:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.96},
  URN =		{urn:nbn:de:0030-drops-73976},
  doi =		{10.4230/LIPIcs.ICALP.2017.96},
  annote =	{Keywords: Twisted word equation, EDT0L, virtually free group, context-free group}
}
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 Imprint Privacy Contact