Real computational universality: the word problem for a class of groups with infinite presentation

DOI10.1007/S10208-009-9048-2zbMATH Open1191.03031OpenAlexW2047947448MaRDI QIDQ734136FDOQ734136

Authors: Klaus Meer, Martin Ziegler 

Publication date: 19 October 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2007/877/

Recommendations

• Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• Turing degrees and the word and conjugacy problems for finitely presented groups.
• scientific article; zbMATH DE number 534859
• scientific article; zbMATH DE number 749927
• The word problem for finitary automaton groups
• COMPUTATION IN WORD-HYPERBOLIC GROUPS
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• scientific article; zbMATH DE number 1936760

zbMATH Keywords

real number computationBlum-Shub-Smale modelword problem for groups

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Cites Work

• Title not available (Why is that?)
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Title not available (Why is that?)
• Embedding Theorems for Groups
• Title not available (Why is that?)
• The combinatorial structure of the Hawaiian earring group
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• THE WORD PROBLEM
• Groups, the theory of ends, and context-free languages
• Title not available (Why is that?)
• An explicit solution to Post's problem over the reals
• Accessible telephone directories
• A model-theoretic proof for P ≠ NP over all infinite abelian group
• Quantum automata and algebraic groups
• Separations and transfers in the polynomial hierarchy of infinite abelian groups
• Ordered Rings Over Which Output Sets are Recursively Enumerable Sets
• Computability and the algebra of fields: Some affine constructions
• The Arithmetical Hierarchy Over the Reals
• The P-DNP problem for infinite Abelian groups

Cited In (3)

• Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation
• Logical Approaches to Computational Barriers
• Generalized finite automata over real and complex numbers

This page was built for publication: Real computational universality: the word problem for a class of groups with infinite presentation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q734136)