Art

J-GLOBAL ID：201602220930133773   Reference number：16A1227036

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

ローレンツ格子ガスセルオートマトンモデルにおける予測周期の計算複雑性

Author (3)： 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)
Material： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Trans Fundam Electron Commun Comput Sci (Web))
Volume： E99.A  Issue： 6  Page： 1034-1049(J-STAGE)  Publication year： 2016 
JST Material Number： U0466A  ISSN： 1745-1337  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： automaton ,  *cellular automaton ,  *modeling ,  Lorentz gas ,  *computational complexity ,  property ,  particle ,  lattice gas automaton
Semi thesaurus term： PSPACE完全 ,  *Cellular automaton model ,  particle ,  lattice gas automaton ,  *computational complexity ,  periodic property

Author keywords (5)： cellular automata ,  computational complexity ,  Lorentz lattice gas ,  Langton’s ant ,  PSPACE-complete

JST classification (2)： System programmings in general  (JD03010Y) ,  Theory of computation  (JB02000A)

Reference (21)：

• [1] R. Tamassia and I.G. Tollis, “A unified approach to visibility representations of planar graphs,” Discrete Comput. Geom., vol.1, no.4, pp.321-341, 1986.
• [2] P. Rosenstiehl and R.E. Tarjan, “Rectilinear planar layouts and bipolar orientations of planar graphs,” Discrete Comput. Geom., vol.1, no.4, pp.343-353, 1986.
• [3] “Mathematical entertainments,” The Mathematical Intelligencer, vol.15, no.2, pp.54-58, 1993.
• [4] A. Gajardo, E. Goles, and A. Moreira, “Generalized Langton's ant: Dynamical behavior and complexity,” STACS 2001, Lecture Notes in Computer Science, vol.2010, pp.259-270, Springer Berlin Heidelberg, 2001.
• [5] A. Gajardo, A. Moreira, and E. Goles, “Complexity of Langton's ant,” Discrete Appl. Math., vol.117, no.1-3, pp.41-50, 2002.

Terms in the title (5)： 格子ガス ,  セルオートマトンモデル ,  予測 ,  周期 ,  計算複雑性