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

  一般社団法人 電子情報通信学会

キーワード

• cellular automata
• computational complexity
• Lorentz lattice gas
• Langton's ant
• PSPACE-complete

詳細情報

• CRID: 1390282681286613120
• NII論文ID: 130005154210
• DOI: 10.1587/transfun.e99.a.1034
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E99.A/6/E99.A_1034/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可