Lakehead University Library Logo
    • Login
    View Item 
    •   Knowledge Commons Home
    • Electronic Theses and Dissertations
    • Retrospective theses
    • View Item
    •   Knowledge Commons Home
    • Electronic Theses and Dissertations
    • Retrospective theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    quick search

    Browse

    All of Knowledge CommonsCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDisciplineAdvisorCommittee MemberThis CollectionBy Issue DateAuthorsTitlesSubjectsDisciplineAdvisorCommittee Member

    My Account

    Login

    Computation using s-programs

    Thumbnail
    View/Open
    WenY1987m-1b.pdf (5.209Mb)
    Date
    1987
    Author
    Wen, Yandan
    Metadata
    Show full item record
    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
    Collections
    • Retrospective theses [1605]

    Lakehead University Library
    Contact Us | Send Feedback

     

     


    Lakehead University Library
    Contact Us | Send Feedback