Automata of Box-Ball Systems and their Filtrons
Poznan University of Technology
Last modified: June 22, 2007
Filtrons of automata are periodic patterns of symbols, specifically substrings of a string, that propagate throughout the cellular nets. These discrete coherent structures owe their existence to iterated automata mappings (IAMs) that are performed along net nodes. In many aspects the filtrons are like solitons well known from nonlinear physics; e.g. they pass through one another, demonstrate elastic collisions, undergo fusion, fission and annihilation, and form breathers as well as other complex periodic entities. Filtrons differ from particles or signals which are considered widely in cellular automata (CAs). They emerge in serial sequential processing of strings.
The first model capable of supporting such coherent objects, PRFCA (parity rule filter cellular automaton), was introduced by Park, Steiglitz and Thurston. After that, a number of models were identified of possessing this ability. These are: filter CAs, soliton CAs, higher order CAs, sequentially updated CAs, integrable CAs, iterated arrays, IIR digital filters or filter automata and so called fast rules. All these models perform sequential processing of strings. Then, also some discrete versions of classical soliton equations (KdV, KP, L-V) were shown to support discrete coherent structures. Finally, the concept of box-ball systems (BBSs) has been introduced by Takahashi. Since that time, many variations of basic BBS model has been proposed in literature, all based on some rearrangements of balls distributed over a line of boxes. The interpretation how string symbols are represented by ball contents of boxes is of importance, as well. Among various families of BBSs there are: single and multiple ball models, models where balls have identifiers, models with carriers of restricted capacity and/or of restricted capacity of boxes, and with mixed finite/infinite capacities. New BBSs appeared in the context of crystal systems, and quantum affine Lie algebras. In these models the idea of order of balls plays a role. In addition, some operations can be applied over balls or between the balls when they are moved along the boxes. Various boundary conditions can be assumed, too. It seems that plethora of models capable of supporting discrete solitons has been opened.
In the paper we show that all these models and their coherent objects can be described and analyzed in a unified manner, namely by finite or infinite state sequential automata. We found and present automata equivalents for all known models of BBSs. The proposed automata differ in their organization of memory: they make use of counters, queues, stacks and sorted lists, which all are of either finite or infinite capacity, but they all support filtrons. It seems that this unified automaton approach discloses the basic computational mechanism that governs nonlinear phenomena of discrete solitons. The gist of this mechanism are iterated automata maps–IAMs, and the filtrons are emerging structures of these IAMs.
The aim of research over automata and their filtrons is not cognitive only. The presented approach helps to characterize transmission abilities of automaton media, thus implies important immediate applications, especially in telecommunications and in the photonic pipelined fibre-based computations in the so-called solitonic processors. In both domains, the problem of designing properly the automata capable of transforming specially shaped impulses and supporting moving coherent structures is of fundamental importance.