Rice Univesrity Logo
    • FAQ
    • Deposit your work
    • Login
    View Item 
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    The structure and behavior of cellular automata

    Thumbnail
    Name:
    RICE0306.pdf
    Size:
    2.201Mb
    Format:
    PDF
    View/Open
    Author
    Kirtane, Jayant Shreedhar
    Date
    1972
    Advisor
    Jump, J. Robert
    Degree
    Master of Science
    Abstract
    A cellular automaton (or CA) is an interconnected set of finite state machines (or cells) such that the inputs of each cell are connected to the outputs of k "neighboring" cells, and the next state of each cell is a function of the present states of its neighboring cells. A CA is uniform if its connection graph is an edge labelled group graph [E.G. WAGNER, IEEE Trans. Elec. Comp., EC-15 (1966), pp 861-873]. A structural homomorphism exists from a CA N1 onto another CA N2 if N2 can effectively be "embedded" in N1. It is proved that neighborhood preserving functions [H. YAMADA and S. AMOROSO, Info. Contr. 18 (1971), pp 1-32] are equivalent to graphical homomorphisms that preserve edge labelling. It is shown that a sufficient condition for the existence of a structural homomorphism from some uniform CA onto another CA N2 is that any cell in N2 be the ith neighbor of exactly one cell in the CA, for all i, Furthermore, when N2 has a finite number of cells, this condition is also necessary. If N2 meets this condition, then a method is shown to construct the smallest CA N1 such
    Citation
    Kirtane, Jayant Shreedhar. "The structure and behavior of cellular automata." (1972) Master’s Thesis, Rice University. https://hdl.handle.net/1911/89269.
    Metadata
    Show full item record
    Collections
    • Rice University Electronic Theses and Dissertations [13409]

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map

     

    Searching scope

    Browse

    Entire ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsTypeThis CollectionBy Issue DateAuthorsTitlesSubjectsType

    My Account

    Login

    Statistics

    View Usage Statistics

    Home | FAQ | Contact Us | Privacy Notice | Accessibility Statement
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
    Site Map