The Library
Solving the word problem in real time
Tools
Tools
Tools
UNSPECIFIED. (2001) Solving the word problem in real time. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 63 (Part 3). pp. 623-639. ISSN 0024-6107
Full text not available from this repository.Abstract
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.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Journal or Publication Title: | JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES |
| Publisher: | LONDON MATH SOC |
| ISSN: | 0024-6107 |
| Date: | June 2001 |
| Volume: | 63 |
| Number: | Part 3 |
| Number of Pages: | 17 |
| Page Range: | pp. 623-639 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/11932 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
