LCS Publication Details
Publication Title: A SPACE BOUND FOR ONE-TAPE MULTIDIMENSIONAL TURING MACHINES
Publication Author: Loui, Michael C.
Additional Authors:
LCS Document Number: MIT-LCS-TM-145
Publication Date: 11-1-1979
LCS Group: No Group Specified
Additional URL: No URL Given
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 deterministic Turing machine of space complexity (T(n) log T(n))did+! The proof employs a generalized crossing sequence argument.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.