Preface
Teijiro Isokawa, Katsunobu Imai, Nobuyuki Matsui, Ferdinand Peper, and Hiroshi Umeo
AUTOMATA 2014 is the 20th International Workshop on Cellular Automata and Discrete Complex Systems and continues a series of events established in 1995. AUTOMATA is an annual workshop and aims of the workshop are:
- To establish and maintain a permanent, international, multidisciplinary forum for the collaboration of researchers in the field of Cellular Automata (CA) and Discrete Complex Systems (DCS).
- To provide a platform for presenting and discussing new ideas and results.
- To support the development of theory and applications of CA and DCS (e.g. parallel computing, physics, biology, social sciences, and others) as long as fundamental aspects and their relations are concerned.
- To identify and study within an inter- and multidisciplinary context, the important fundamental aspects, concepts, notions and problems concerning CA and DCS.
AUTOMATA 2014, held in Himeji, Japan, from July 7 to July 9, 2014, is the result of cooperation of the institutions of the members of the organizing committee. The accepted regular papers have been published as a proceedings of the workshop, in the volume 8996 of Lecture Notes in Computer Sciences (LNCS), 2015.
The volume of this special issue contains five contributions that are extended from the papers in the proceedings of AUTOMATA 2014.
The paper, entitled “Language Recognition by Reversible Partitioned Cellular Automata and Iterative Arrays,” authored by Morita, introduces two kinds of language recognizers based on one-dimensional reversible partitioned cellular automata and shows their capabilities. The accepting powers of these models are shown to be equivalent to deterministic linear-bounded automata.
The second paper is “Computational complexity of the avalanche problem for one dimensional decreasing sandpiles,” authored by Formenti et al. This paper gives a complete proof in which the general avalanche problem follows a complexity of NC1 for all decreasing sandpile models in one-dimensional space.
A problem on a CA-based pseudorandom number generator is described in the paper “Designing Conflict Free Cellular Automata-Based PRNG,” authored by Szaban et al. It is shown that a new set of transition rules for one-dimensional CA provides cryptographically strong bit sequences and a huge key space.
Hazari et al. explores elementary CAs with asynchronous update in the paper entitled ”Number Conservation Property of Binary Cellular Automata under α-Asynchronous Update.” The cells are updated in asynchronous modes with a parameter α, and a set of elementary CAs is shown to have probabilistic number conserving properties.
The last paper, entitled “Introducing Lyapunov profiles of cellular automata,” authored by Baetens et al, proposes new Lyapunov profiles that characterize the dynamics of CAs. The behavior of elementary CAs is measured and analyzed by these profiles under the condition that defective cells are included in the cellular space.
We thank all authors for their excellent contributions, and we are grateful to the reviewers who spared their time to review these contributions.
Teijiro Isokawa
Katsunobu Imai
Nobuyuki Matsui
Ferdinand Peper
Hiroshi Umeo
March, 2017