Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Sénizergues, Géraud; Weiß, Armin http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-91437
URL:

;

The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE

pdf-format:


Abstract

We present an algorithm for the following problem: given a context-free grammar for the word problem of a virtually free group G, compute a finite graph of groups G with finite vertex groups and fundamental group G. Our algorithm is non-deterministic and runs in doubly exponential time. It follows that the isomorphism problem of context-free groups can be solved in doubly exponential space. Moreover, if, instead of a grammar, a finite extension of a free group is given as input, the construction of the graph of groups is in NP and, consequently, the isomorphism problem in PSPACE.

BibTeX - Entry

@InProceedings{snizergues_et_al:LIPIcs:2018:9143,
  author =	{G{\'e}raud S{\'e}nizergues and Armin Wei{\ss}},
  title =	{{The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{139:1--139:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9143},
  URN =		{urn:nbn:de:0030-drops-91437},
  doi =		{10.4230/LIPIcs.ICALP.2018.139},
  annote =	{Keywords: virtually free groups, context-free groups, isomorphism problem, structure tree, graph of groups}
}

Keywords: virtually free groups, context-free groups, isomorphism problem, structure tree, graph of groups
Seminar: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue date: 2018
Date of publication: 2018


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