Displaying similar documents to “An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem”

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...

Deterministic blow-ups of minimal NFA's

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

The paper treats the question whether there always exists a minimal nondeterministic finite automaton of states whose equivalent minimal deterministic finite automaton has states for any integers and with . Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of and . However, in order to give an...

Number-conserving reversible cellular automata and their computation-universality

Kenichi Morita, Katsunobu Imai (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We introduce a new model of cellular automaton called a one-dimensional number-conserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that a state of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) of integers over the configuration is conserved throughout its evolving (computing) process. It can be thought as a kind of modelization of the physical conservation law of mass (particles) or energy. We also define a reversible...