Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1034-1049
- Publication Date
- 2016/06/01
- Publicized
- 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
Authors
Takeo HAGIWARA
Tokyo Denki University
Tatsuie TSUKIJI
Tokyo Denki University
Zhi-Zhong CHEN
Tokyo Denki University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takeo HAGIWARA, Tatsuie TSUKIJI, Zhi-Zhong CHEN, "Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1034-1049, June 2016, doi: 10.1587/transfun.E99.A.1034.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1034/_p
Copy
@ARTICLE{e99-a_6_1034,
author={Takeo HAGIWARA, Tatsuie TSUKIJI, Zhi-Zhong CHEN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata},
year={2016},
volume={E99-A},
number={6},
pages={1034-1049},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.1034},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1034
EP - 1049
AU - Takeo HAGIWARA
AU - Tatsuie TSUKIJI
AU - Zhi-Zhong CHEN
PY - 2016
DO - 10.1587/transfun.E99.A.1034
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - 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.
ER -
English
