The complexity of Dehn's algorithm for word problems in groups |
| |
| Authors: | B Domanski M Anshel |
| |
| Institution: | College of Staten Island, CUNY, Staten Island, New York 10301 USA;City College of New York, CUNY, New York, New York 10033 USA |
| |
| Abstract: | Given the presentation for a group of Dehn's algorithm, a multitape Turing machine is shown to exist that solves the word problem for that presentation in linear time. Key to this solution is the pattern matching methodology from complexity theory as well as a recent result for confluent Thue systems. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
