License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8773
URL: http://drops.dagstuhl.de/opus/volltexte/2007/877/

Meer, Klaus ; Ziegler, Martin

Real Computational Universality: The Word Problem for a class of groups with infinite presentation

pdf-format:
Dokument 1.pdf (200 KB)


Abstract

In this talk we introduce a class of groups represented as quotient groups of some free groups generated by infinitely many elements and certain normal subgroups. We show that the related word problem is universal in the Blum-Shub-Smale model of computation, i.e. it has the same difficulty as the real Halting Problem. This is the first natural example of a problem with this property. The work has been done jointly with Martin Ziegler.

BibTeX - Entry

@InProceedings{meer_et_al:DSP:2007:877,
  author =	{Klaus Meer and Martin Ziegler},
  title =	{Real Computational Universality: The Word Problem for a class of groups with infinite presentation},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  year =	{2007},
  editor =	{Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub},
  number =	{06391},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/877},
  annote =	{Keywords: Computational group theory, word problem, Blum-Shub-Smale model}
}

Keywords: Computational group theory, word problem, Blum-Shub-Smale model
Seminar: 06391 - Algorithms and Complexity for Continuous Problems
Issue date: 2007
Date of publication: 31.01.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI