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
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 |