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

Meer, Klaus; Ziegler, Martin

doi:10.4230/DagSemProc.06391.2

Document

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

Authors Klaus Meer, Martin Ziegler

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 6391
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2007-01-31

PDF

File

PDF

DagSemProc.06391.2.pdf

Filesize: 200 kB
20 pages

Document Identifiers

DOI: 10.4230/DagSemProc.06391.2
URN: urn:nbn:de:0030-drops-8773

Subject Classification

Keywords

Computational group theory
word problem
Blum-Shub-Smale model

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Klaus Meer and Martin Ziegler. Real Computational Universality: The Word Problem for a class of groups with infinite presentation. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 6391, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007) https://doi.org/10.4230/DagSemProc.06391.2

Author Details

Klaus Meer

Martin Ziegler

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail