dc.contributor.author Hunt, Harry B., III en_US dc.date.accessioned 2007-04-19T19:04:04Z dc.date.available 2007-04-19T19:04:04Z dc.date.issued 1973-08 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-182 en_US dc.identifier.uri https://hdl.handle.net/1813/6025 dc.description.abstract We investigate the following: (1) the relationship between the classes of languages accepted by deterministic and nondeterministic polynomial time bounded Turing machines; (2) the relationship between the classes of languages accepted by deterministic and nondeterministic linear bounded automata; (3) sufficient conditions for undecidability of linguistic predicates; and (4) the time and space complexity of several predicates on the regular sets. We show that the set $\{ R | R$ is a $(\cup, ^{.}, *, \caap)$ regular expression and $L(R) = \{0,1\}*\}$ is not recognizable by any polynomial space bounded Turing machine. We also find conditions which guarantee that any predicate on the regular sets satisfying them is as hard to decide as emptiness or equivalence. en_US dc.format.extent 4628963 bytes dc.format.extent 960808 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title On the Time and Tape Complexity of Languages en_US dc.type technical report en_US
﻿