Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Meer, Klaus; Ziegler, Martin License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8773
URL:

;

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

pdf-format:


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
Related Scholarly Article:
Issue date: 2007
Date of publication: 2007


DROPS-Home | Fulltext Search | Imprint Published by LZI