Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata
-
- HAGIWARA Takeo
- Department of Informatics, Tokyo Denki University
-
- TSUKIJI Tatsuie
- Department of Informatics, Tokyo Denki University
-
- CHEN Zhi-Zhong
- Department of Informatics, Tokyo Denki University
抄録
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.
収録刊行物
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E99.A (6), 1034-1049, 2016
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282681286613120
-
- NII論文ID
- 130005154210
-
- ISSN
- 17451337
- 09168508
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可