On real time and linear time cellular automata
W. Bucher, K. Culik II (1984)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Displaying similar documents to “Language classes defined by time-bounded relativised cellular automata”
On real time and linear time cellular automata
Nondeterministic forgetting automata are less powerful than deterministic linear bounded automata
Petr Jančar (1993)
Acta Mathematica et Informatica Universitatis Ostraviensis
Similarity:
Some remarks on multihead automata
I. H. Sudborough (1977)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Two-way multihead automata over a one-letter alphabet
Burkhard Monien (1980)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Some results on cellular automata
Claudio Baiocchi (1998)
Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni
Similarity:
We want to discuss some properties of one-dimensional, radius 1, CUCAs (we denote by CUCA a Computationally Universal Cellular Automaton; see later on for the definitions). In particular, on one hand we want to keep small the number of states (the first example of «small» CUCA is due to Smith III [13]; it requires 18 states); on the other hand we are interested into automata, possibly requiring a high number of states, whose transition law is «as simple as possible»; e.g. totalistic...