TY - GEN
T1 - Generalized langton's ant
T2 - 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001
AU - Gajardo, Anahí
AU - Goles, Eric
AU - Moreira, Andrés
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.
PY - 2001
Y1 - 2001
N2 - Langton's ant is a simple discrete dynamical system, with a surprisingly complex behavior. We study its extension to general planar graphs. First we give some relations between characteristics of finite graphs and the dynamics of the ant on them. Then we consider the infinite bi-regular graphs of degrees 3 and 4, where we prove the universality of the system, and in the particular cases of the square and the hexagonal grids, we associate a P-hard problem to the dynamics. Finally, we show strong spatial restrictions on the trajectory of the ant in infinite bi-regular graphs with degrees strictly greater than 4, which contrasts with the high unpredictability on the graphs of lower degrees.
AB - Langton's ant is a simple discrete dynamical system, with a surprisingly complex behavior. We study its extension to general planar graphs. First we give some relations between characteristics of finite graphs and the dynamics of the ant on them. Then we consider the infinite bi-regular graphs of degrees 3 and 4, where we prove the universality of the system, and in the particular cases of the square and the hexagonal grids, we associate a P-hard problem to the dynamics. Finally, we show strong spatial restrictions on the trajectory of the ant in infinite bi-regular graphs with degrees strictly greater than 4, which contrasts with the high unpredictability on the graphs of lower degrees.
UR - http://www.scopus.com/inward/record.url?scp=23044526639&partnerID=8YFLogxK
U2 - 10.1007/3-540-44693-1_23
DO - 10.1007/3-540-44693-1_23
M3 - Conference contribution
AN - SCOPUS:23044526639
SN - 9783540416951
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 259
EP - 270
BT - STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
A2 - Ferreira, Afonso
A2 - Reichel, Horst
PB - Springer Verlag
Y2 - 15 February 2001 through 17 February 2001
ER -