License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06391.2
URN: urn:nbn:de:0030-drops-8773
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/877/
Go to the corresponding Portal

Meer, Klaus ; Ziegler, Martin

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

pdf-format:
06391.MeerKlaus.Paper.877.pdf (0.2 MB)

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:DagSemProc.06391.2,
  author =	{Meer, Klaus and Ziegler, Martin},
  title =	{{Real Computational Universality: The Word Problem for a class of groups with infinite presentation}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6391},
  editor =	{Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/877},
  URN =		{urn:nbn:de:0030-drops-8773},
  doi =		{10.4230/DagSemProc.06391.2},
  annote =	{Keywords: Computational group theory, word problem, Blum-Shub-Smale model}
}

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

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