Box-ball system

Box-ball systems (BBS) are a family of reversible cellular automaton (CA) introduced by Daisuke Takahashi and Junkichi Satsuma in 1990.^[1] The denomination derives from a simple behavioral model: A finite collection of colored balls moves about an array of boxes of finite capacity indexed by the integers. Time is also indexed by the integers; during each time step the balls move in the following manner: In order of color, then in order from left to right, each ball moves to the first box below capacity to its right. In 2001 Kaori Fukuda reinterpreted box-ball algorithms in the language of tableaux.^[2]

Original BBS

The simplest box-ball systems reduce all balls to uniform color and all boxes to capacity 1; they are therefore two-state, one-dimensional CAs. (Boxes serve as cells with states 0 (vacant) and 1 (occupied); at any given time only finitely many boxes are occupied.) The system evolves in the following manner: At each time step, in order from left to right, each ball moves to the nearest vacant box to its right. Observe the sample time steps below:

t = 0 | … 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 …
t = 1 | … 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 …
t = 2 | … 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 …
t = 3 | … 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 …
t = 4 | … 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 …
t = 5 | … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 …

The system is reversible in that any given state can follow only one previous state, called a preimage. This property is most clearly seen in box-ball systems by evolving the system upward with balls moving, in order from right to left, to the nearest vacant boxes on their lefts (effectively rotating the picture above 180 degrees).

An important feature of box-ball systems are the so-called "basic strings" (BS's) roughly defined as follows: Find the first maximal string of only 0s or only 1s no longer than the one to its immediate right, and denote its length m. Label each element of the string and the leftmost m elements of the adjacent string with the number m. Now remove these 2m elements from consideration, yielding a new system with fewer 1s. Repeat this process until all 1s (and as many 0s) have been labeled.

… 0 0 0 1⁴1⁴1⁴1⁴0⁴0⁴0⁴0⁴0 1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 …
… 0 0 0 1⁴1⁴1⁴1⁴0⁴0⁴0⁴0⁴0 1 1 0¹1¹0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 …
… 0 0 0 1⁴1⁴1⁴1⁴0⁴0⁴0⁴0⁴0 1²1²0¹1¹0²0²0 1 0 0 1 1 1 0 0 0 0 0 0 …
… 0 0 0 1⁴1⁴1⁴1⁴0⁴0⁴0⁴0⁴0 1²1²0¹1¹0²0²0 1¹0¹0 1 1 1 0 0 0 0 0 0 …
… 0 0 0 1⁴1⁴1⁴1⁴0⁴0⁴0⁴0⁴0 1²1²0¹1¹0²0²0 1¹0¹0 1³1³1³0³0³0³0 0 0 …

These basic strings are preserved across time steps in the sense that, for every time step in a given system, the number of elements labeled m is fixed for each natural number m. The maximal strings of (1s) are then solitons, for their structure is preserved; the box-ball system is therefore a soliton automaton. The BS's eventually separate in increasing order of length, as has occurred by the last time step below. Each BS of length m then moves at speed m (shifting m cells in each time step) thereafter. (By reversibility, it is also true that, far enough back in time, the BS's are separate in decreasing order of length and speed.)

t = 0 | … 0 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 …
t = 1 | … 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 …
t = 2 | … 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 …
t = 3 | … 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 …
t = 4 | … 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 …
t = 5 | … 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 …
Legend: m = 1, m = 2, m = 3, m = 4

Standard BBS

Generalized BBS

Carrier algorithms and evolution of tableaux

Notes and References

^ Takahashi, Daisuke and Satsuma, Junkichi (1990). "A Soliton Cellular Automaton". Journal of The Physical Society of Japan 59 (10), 3514–3519.
^ Fukuda, Kaori (2003). "Box-Ball Systems and Robinson–Schensted–Knuth Correspondence". Journal of Algebraic Combinatorics 19, 67–89.

Defining function

In the theory of functions of several complex variables, a defining function for a domain in $\mathbb {C} ^{n}$ with "continuous" boundary is a continuous real-valued function on $\mathbb {C} ^{n}$ (or smaller region containing the boundary of the domain) which is negative-valued precisely at points in the domain and has nonzero gradient on its boundary. The continuity of this function is taken to be the continuity of the boundary of the domain.

Definitions

A domain $\Omega \subseteq \mathbb {C} ^{n}$ has $C^{k}$ boundary if there exists a $C^{k}$ function $\rho :\mathbb {C} ^{n}\rightarrow \mathbb {R}$ (that is, a continuous real-valued function on $\mathbb {C} ^{n}$ with continuous first through kth derivatives) which exhibits

\{z:\rho (z)<0\}=\Omega

and

\mathrm {grad} \rho (z)\neq 0

for

z\in \partial \Omega

(the boundary of

\Omega

).

Thus, $\rho (z_{1},\ldots ,z_{n})<0\Leftrightarrow (z_{1},\ldots ,z_{n})\in \Omega$ . $\rho$ is then called a defining function for $\Omega$ .

Under some definitions, $\rho$ need only be defined on some neighbourhood $U$ of $\partial \Omega$ , so that $[f>0]=\Omega \cap U$ , but these two definitions are equivalent.

References

^ S. G. Krantz (1982). Function Theory of Several Complex Variables. John Wiley & Sons. ISBN 0821827243.