Wyniki wyszukiwania - BazTech

1

Automorphism Classification of Cellular Automata

Nishio H.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

125-140

EN

A new classification of arbitrary cellular automata (CA for short) in Z^d is studied considering the set (group) of all permutations of the neighborhood v and state set Q. Two CA (Z^d, Q, f_A, .A) and (Z^d, Q, f_B, v_B) are called automorphic, if there is a pair of permutationsπ&pfi" of v and Q, respectively, such that (f_B, vB) = ([formula] where v^π denotes a permutation of v and f*π denotes a permutation of arguments of local function f corresponding to v*π This automorphism naturally induces a classification of CA, such that it generally preserves the global properties of CA up to permutation. As a typical example of the theory, the local functions of 256 ECA (1- dimensional 3-nearest neighbors 2-states CA) are classified into 46 classes. We also give a computer test of surjectivity, injecitivity and reversibility of the classes.

2

On Algebraic Structure of Neighborhoods of Cellular Automata-Horse Power Problem-

Nishio H., Margenstern M., Haeseler F. von

Fundamenta Informaticae

|

2007

|

Vol. 78, nr 3

397-416

EN

In a previous paper we formulated and analyzed the structure of neighborhoods of cellular automata in an algebraic setting such that the cellular space S is represented by the Cayley graph of a finitely generated group and the neighbors are defined as a semigroup generated by the neighborhood N as a subset of S, Nishio and Margenstern 2004 [14,15]. Particularly we discussed the horse power problem whether the motion of a horse (knight) fills the infinite chess board or Z^2- that is, an algebraic problem whether a subset of a group generates it or not. Among others we proved that a horse fills Z^2 even when its move is restricted to properly chosen 3 directions and gave a necessary and sufficient condition for a generalized 3-horse to fill Z^2. This paper gives further developments of the horse power problem, say, on the higher dimensional Euclidean grid, the hexagonal grid and the hyperbolic plane.

3

Information Dynamics of Cellular Automata I -An Algebraic Study

Nishio H., Saito T.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 3,4

399--420

EN

Information dynamics of cellular automata(CA) is studied using polynomials over finite fields. The information about the uncertainty of cell states is expressed by an indeterminate X called information variable and its dynamics is investigated by extending CA to CA[X] whose cell states are polynomials in X. For the global configuration of extended CA[X], new notions of completeness and degeneracy are defined and their dynamical properties are investigated. A theorem is proved that completeness equals non-degeneracy. With respect to the reversibility, we prove that a CA is reversible, if and only if its extension CA[X] preserves the set of complete configurations. Information dynamics of finite CAs and linear CAs are treated in the separate sections. Decision problems are also referred.