The Library
On real-time word problems
Tools
Holt, Derek F. and Röver, Claas E. (2003) On real-time word problems. Journal of the London Mathematical Society, Vol.67 (No.2). pp. 289-301. doi:10.1112/S0024610702003770 ISSN 0024-6107.
|
PDF
WRAP_Holt_Real-time_word.pdf - Requires a PDF viewer. Download (250Kb) |
Official URL: http://dx.doi.org/10.1112/S0024610702003770
Abstract
It is proved that the word problem of the direct product of two free groups of rank 2 can be recognised by a 2-tape real-time but not by a 1-tape real-time Turing machine. It is also proved that the Baumslag–Solitar groups B(1,r) have the 5-tape real-time word problem for all r != 0.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Word problems (Mathematics), Turing machines, Combinatorial group theory, Geometric group theory | ||||
Journal or Publication Title: | Journal of the London Mathematical Society | ||||
Publisher: | Cambridge University Press | ||||
ISSN: | 0024-6107 | ||||
Official Date: | April 2003 | ||||
Dates: |
|
||||
Volume: | Vol.67 | ||||
Number: | No.2 | ||||
Page Range: | pp. 289-301 | ||||
DOI: | 10.1112/S0024610702003770 | ||||
Status: | Peer Reviewed | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year