A Space Bound for One-tape Multidimensional Turing Machines
| dc.contributor.author | Loui, Michael C. | en_US |
| dc.date.accessioned | 2023-03-29T14:15:11Z | |
| dc.date.available | 2023-03-29T14:15:11Z | |
| dc.date.issued | 1979-11 | |
| dc.identifier.uri | https://hdl.handle.net/1721.1/148972 | |
| dc.description.abstract | Let L be a language recognized by a nondeterministic Turing machine with one d-dimensional worktape of time complexity T(n). Then L can be recognized by a deterministic Turing machine of space complexity (T(n)logT(n))^d/d+1. The prood employs a generalized crossing sequence argument. | en_US |
| dc.relation.ispartofseries | MIT-LCS-TM-145 | |
| dc.title | A Space Bound for One-tape Multidimensional Turing Machines | en_US |
| dc.identifier.oclc | 6076897 |
