Displaying similar documents to “Gardens of Eden and amenability on cellular automata”

Amenability of linear-activity automaton groups

Gideon Amir, Omer Angel, Bálint Virág (2013)

Journal of the European Mathematical Society

Similarity:

We prove that every linear-activity automaton group is amenable. The proof is based on showing that a random walk on a specially constructed degree 1 automaton group – the mother group – has asymptotic entropy 0. Our result answers an open question by Nekrashevych in the Kourovka notebook, and gives a partial answer to a question of Sidki.

Amenable groups and cellular automata

Tullio G. Ceccherini-Silberstein, Antonio Machi, Fabio Scarabotti (1999)

Annales de l'institut Fourier

Similarity:

We show that the theorems of Moore and Myhill hold for cellular automata whose universes are Cayley graphs of amenable finitely generated groups. This extends the analogous result of A. Machi and F. Mignosi “Garden of Eden configurations for cellular automata on Cayley graphs of groups” for groups of sub-exponential growth.

Systems of parallel communicating restarting automata

Marcel Vollweiler, Friedrich Otto (2014)

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

Similarity:

Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols,...

How expressions can code for automata

Sylvain Lombardy, Jacques Sakarovitch (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper we investigate how it is possible to recover an automaton from a rational expression that has been computed from that automaton. The notion of derived term of an expression, introduced by Antimirov, appears to be instrumental in this problem. The second important ingredient is the co-minimization of an automaton, a dual and generalized Moore algorithm on non-deterministic automata.
We show here that if an automaton is then sufficiently “decorated”, the combination...

Returning and non-returning parallel communicating finite automata are equivalent

Ashish Choudhary, Kamala Krithivasan, Victor Mitrana (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.

The entropy of Łukasiewicz-languages

Ludwig Staiger (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.