SOLVING THE WORD PROBLEM IN REAL TIME
Copyright policy )SOLVING THE WORD PROBLEM IN REAL TIME
The paper is devoted to the study of groups whose word problem can be solved by a Turing machine which operates in real time. A recent result of the first author for word hyperbolic groups is extended to prove that under certain conditions the generalised Dehn algorithms of Cannon, Goodman and Shapiro, which clearly run in linear time, can be programmed on real-time Turing machines. It follows that word-hyperbolic groups, finitely generated nilpotent groups and geometrically finite hyperbolic groups all have real-time word problems.
- University of Warwick United Kingdom
- University of Newcastle Australia Australia
- Newcastle University United Kingdom
Hyperbolic groups and nonpositively curved groups, word problem, Dehn algorithms, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), real-time Turing machines, word-hyperbolic groups, QA, Word problems, etc. in computability and recursion theory, Cancellation theory of groups; application of van Kampen diagrams
Hyperbolic groups and nonpositively curved groups, word problem, Dehn algorithms, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), real-time Turing machines, word-hyperbolic groups, QA, Word problems, etc. in computability and recursion theory, Cancellation theory of groups; application of van Kampen diagrams
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).8 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!