The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] Langton's ant(1hit)

1-1hit
  • Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata

    Takeo HAGIWARA  Tatsuie TSUKIJI  Zhi-Zhong CHEN  

     
    PAPER

      Vol:
    E99-A No:6
      Page(s):
    1034-1049

    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.