3 Search Results for "Bartholdi, Laurent"

Document
DOI: 10.4230/LIPIcs.CCC.2020.29
Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems

Authors: Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We give lower bounds on the complexity of the word problem of certain non-solvable groups: for a large class of non-solvable infinite groups, including in particular free groups, Grigorchuk’s group and Thompson’s groups, we prove that their word problem is ALOGTIME-hard. For some of these groups (including Grigorchuk’s group and Thompson’s groups) we prove that the circuit value problem (which is equivalent to the circuit evaluation problem) is PSPACE-complete.
Cite as

Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß. Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 29:1-29:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bartholdi_et_al:LIPIcs.CCC.2020.29,
  author =	{Bartholdi, Laurent and Figelius, Michael and Lohrey, Markus and Wei{\ss}, Armin},
  title =	{{Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{29:1--29:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.29},
  URN =		{urn:nbn:de:0030-drops-125814},
  doi =		{10.4230/LIPIcs.CCC.2020.29},
  annote =	{Keywords: NC^1-hardness, word problem, G-programs, straight-line programs, non-solvable groups, self-similar groups, Thompson’s groups, Grigorchuk’s group}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.43
The Power Word Problem

Authors: Markus Lohrey and Armin Weiß

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In this work we introduce a new succinct variant of the word problem in a finitely generated group G, which we call the power word problem: the input word may contain powers p^x, where p is a finite word over generators of G and x is a binary encoded integer. The power word problem is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over G). The main result of the paper states that the power word problem for a finitely generated free group F is AC^0-Turing-reducible to the word problem for F. Moreover, the following hardness result is shown: For a wreath product G Wr Z, where G is either free of rank at least two or finite non-solvable, the power word problem is complete for coNP. This contrasts with the situation where G is abelian: then the power word problem is shown to be in TC^0.
Cite as

Markus Lohrey and Armin Weiß. The Power Word Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.MFCS.2019.43,
  author =	{Lohrey, Markus and Wei{\ss}, Armin},
  title =	{{The Power Word Problem}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.43},
  URN =		{urn:nbn:de:0030-drops-109871},
  doi =		{10.4230/LIPIcs.MFCS.2019.43},
  annote =	{Keywords: word problem, compressed word problem, free groups}
}
Document
DOI: 10.4230/LIPIcs.CPM.2019.18
On Maximal Repeats in Compressed Strings

Authors: Julian Pape-Lange

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract
This paper presents and proves a new non-trivial upper bound on the number of maximal repeats of compressed strings. Using Theorem 1 of Raffinot’s article "On Maximal Repeats in Strings", this upper bound can be directly translated into an upper bound on the number of nodes in the Compacted Directed Acyclic Word Graphs of compressed strings. More formally, this paper proves that the number of maximal repeats in a string with z (self-referential) LZ77-factors and without q-th powers is at most 3q(z+1)^3-2. Also, this paper proves that for 2000 <= z <= q this upper bound is tight up to a constant factor.
Cite as

Julian Pape-Lange. On Maximal Repeats in Compressed Strings. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{papelange:LIPIcs.CPM.2019.18,
  author =	{Pape-Lange, Julian},
  title =	{{On Maximal Repeats in Compressed Strings}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.18},
  URN =		{urn:nbn:de:0030-drops-104898},
  doi =		{10.4230/LIPIcs.CPM.2019.18},
  annote =	{Keywords: Maximal repeats, Combinatorics on compressed strings, LZ77, Compact suffix automata, CDAWGs}
}
  • Refine by Author
  • 2 Lohrey, Markus
  • 2 Weiß, Armin
  • 1 Bartholdi, Laurent
  • 1 Figelius, Michael
  • 1 Pape-Lange, Julian

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Circuit complexity
  • Show More...

  • Refine by Keyword
  • 2 word problem
  • 1 CDAWGs
  • 1 Combinatorics on compressed strings
  • 1 Compact suffix automata
  • 1 G-programs
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2020

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