Show simple item record

dc.contributor.authorHunt, Harry B., IIIen_US
dc.date.accessioned2007-04-19T19:04:04Z
dc.date.available2007-04-19T19:04:04Z
dc.date.issued1973-08en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-182en_US
dc.identifier.urihttps://hdl.handle.net/1813/6025
dc.description.abstractWe 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.extent4628963 bytes
dc.format.extent960808 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn the Time and Tape Complexity of Languagesen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics