For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata
Takeo HAGIWARA Tatsuie TSUKIJI Zhi-Zhong CHEN
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/06/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
cellular automata, computational complexity, Lorentz lattice gas, Langton's ant, PSPACE-complete,
Full Text: PDF>>
Some diffusive and recurrence properties of Lorentz Lattice Gas Cellular Automata (LLGCA) have been expensively studied in terms of the densities of some of the left/right static/flipping mirrors/rotators. In this paper, for any combination S of these well known scatters, we study the computational complexity of the following problem which we call PERIODICITY on the S-model: given a finite configuration that distributes only those scatters in S, whether a particle visits the starting position periodically or not. Previously, the flipping mirror model and the occupied flipping rotator model have been shown unbounded, i.e. the process is always diffusive . On the other hand, PERIODICITY is shown PSPACE-complete in the unoccupied flipping rotator model . In this paper, we show that PERIODICITY is PSPACE-compete in any S-model that is neither occupied, unbounded, nor static. Particularly, we prove that PERIODICITY in any unoccupied and bounded model containing flipping mirror is PSPACE-complete.