Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata

Takeo HAGIWARA  Tatsuie TSUKIJI  Zhi-Zhong CHEN  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1034-1049
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1034
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cellular automata,  computational complexity,  Lorentz lattice gas,  Langton's ant,  PSPACE-complete,  

Full Text: PDF>>
Buy this Article




Summary: 
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 [17]. On the other hand, PERIODICITY is shown PSPACE-complete in the unoccupied flipping rotator model [21]. 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.