The Library
Groups that do and do not have growing context-sensitive word problem
Tools
Holt, Derek F., Rees, Sarah and Shapiro, Michael (2008) Groups that do and do not have growing context-sensitive word problem. International Journal of Algebra and Computation, Volume 18 (Number 7). pp. 1179-1191. doi:10.1142/S0218196708004834 ISSN 0218-1967.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1142/S0218196708004834
Abstract
We prove that a group has word problem that is a growing context-sensitive language precisely if its word problem can be solved using a non-deterministic Cannon's algorithm (the deterministic algorithms being defined by Goodman and Shapiro in [6]). We generalize results of [6] to find many examples of groups not admitting non-deterministic Cannon's algorithms. This adds to the examples of Kambites and Otto in [7] of groups separating context-sensitive and growing context-sensitive word problems, and provides a new language-theoretic separation result.
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), Formal languages | ||||
Journal or Publication Title: | International Journal of Algebra and Computation | ||||
Publisher: | World Scientific Publishing Co. Pte. Ltd. | ||||
ISSN: | 0218-1967 | ||||
Official Date: | November 2008 | ||||
Dates: |
|
||||
Volume: | Volume 18 | ||||
Number: | Number 7 | ||||
Number of Pages: | 13 | ||||
Page Range: | pp. 1179-1191 | ||||
DOI: | 10.1142/S0218196708004834 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Related URLs: |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |