JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Time and Tape Complexity of Languages
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 |