Complete Symmetry in D2L Systems and Cellular Automata

P.R.J. Asveld

    Research output: Book/ReportReportOther research output

    9 Downloads (Pure)

    Abstract

    We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries we obtain new characterizations of the recursively enumerable languages and of some space-bounded complexity classes.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherUniversity of Twente, Department of Computer Science
    Number of pages12
    Publication statusPublished - 1985

    Publication series

    NameMemoranda Informatica
    PublisherUniversity of Twente, Department of Computer Science
    No.INF-85-19
    ISSN (Print)0924-3755

      Fingerprint

    Keywords

    • HMI-SLT: Speech and Language Technology
    • D2L system
    • Cellular automaton
    • Symmetry
    • Recursively enumerable language (r.e.)
    • Space-bounded complexity class

    Cite this

    Asveld, P. R. J. (1985). Complete Symmetry in D2L Systems and Cellular Automata. (Memoranda Informatica; No. INF-85-19). Enschede: University of Twente, Department of Computer Science.