Please use this identifier to cite or link to this item: https://knowledgecommons.lakeheadu.ca/handle/2453/917
Title: Computation using s-programs
Authors: Wen, Yandan
Keywords: Machine theory;Formal languages
Issue Date: 1987
Abstract: The concepts of S and Sn programs are given by Davis, Weyuker, 1983. Several parts of the complexity theory are carried out directly for S and Sn programs. The concepts of non-deterministic and deterministic computation from S-programs are defined, and deterministic simulation of non-deterministic computation is proved. A universal 5-program for general (non-deterministic) computation is shown to require only one duplicate line label. Complexity results are given for these and other simulations, e.g. Turing Machine by 5-programs and the reverse. Cook's Theorem for Sn programs is proved in full.
URI: http://knowledgecommons.lakeheadu.ca/handle/2453/917
metadata.etd.degree.discipline: Mathematical Sciences
metadata.etd.degree.name: Master of Science
metadata.etd.degree.level: Master
metadata.dc.contributor.advisor: Kent, C. F.
Appears in Collections:Retrospective theses

Files in This Item:
File Description SizeFormat 
WenY1987m-1b.pdf5.33 MBAdobe PDFThumbnail
View/Open


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