Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6007
Title: On the Time and Tape Complexity of Languages, I
Authors: Hunt, Harry B., III
Keywords: computer science
technical report
Issue Date: Jan-1973
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-156
Abstract: We investigate the relationship between the classes of languages accepted by deterministic and nondeterministic polynomial time bounded Turing machines and the relationship between the classes of languages accepted by deterministic polynomial time bounded and by nondeterministic polynomial tape bounded Turing machines. In both cases we study generators of the nondeterministic class that generate it by operations that the deterministic class is closed under.
URI: http://hdl.handle.net/1813/6007
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
73-156.pdf2.24 MBAdobe PDFView/Open
73-156.ps767.55 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us