Takeo Hagiwara

Dr. Takeo Hagiwara

Department of science and engineering, Tokyo Denki University

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
16 December 2020 in Algorithms
Verified
Journal Article
Open access
PDF file
THTakeo Hagiwara
Takeo Hagiwara
Tatsuie TsukijiTatsuie Tsukiji
Tatsuie Tsukiji
Langton’s ant is a deterministic cellular automaton studied in many fields, artificial life, computational complexity, cryptography, emergent dynamics, Lorents lattice gas, and so forth, motivated by the hardness of predicting the ant’s macroscopic behavior from an initial microscopic configuration. Gajardo, Moreira, and Goles (2002) proved that Langton’s ant is PTIME -hard for reachability. On a twisted torus, we demonstrate that it is PSPACE hard to determine whether the ant will ever visit almost all vertices or nearly none of them.