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

Authors Klaus Meer, Martin Ziegler



PDF
Thumbnail PDF

File

DagSemProc.06391.2.pdf
  • Filesize: 200 kB
  • 20 pages

Document Identifiers

Author Details

Klaus Meer
Martin Ziegler

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

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.
Keywords
  • Computational group theory
  • word problem
  • Blum-Shub-Smale model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail