Show simple item record

dc.contributor.advisorKent, C. F.
dc.contributor.authorWen, Yandan
dc.date.accessioned2017-06-05T14:03:45Z
dc.date.available2017-06-05T14:03:45Z
dc.date.created1987
dc.date.issued1987
dc.identifier.urihttp://knowledgecommons.lakeheadu.ca/handle/2453/917
dc.description.abstractThe 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.
dc.language.isoen_US
dc.subjectMachine theory
dc.subjectFormal languages
dc.titleComputation using s-programs
dc.typeThesis
etd.degree.nameMaster of Science
etd.degree.levelMaster
etd.degree.disciplineMathematical Sciences
etd.degree.grantorLakehead University


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record