photo anahi
Anahí Gajardo
Temas de investigación: Sistemas dinámicos discretos, Calculabilidad, Hormiga de Langton. 

Dirección postal:

Casilla 160-C
Concepciión 

Chile

Teléfono: (56-41) 220 7042 


Fax: (56-41) 252 2055 
E-mail: anahi at ing-mat dot udec dot cl 






 
 
Taller de Matemática y Cómputo
Publicaciones
Página de la hormiga de Langton
 
 
 
Nací en Chile, donde he hecho la mayor parte de mis estudios. Estudié ingeniería en la Universidad de Chile y luego hice un doctorado en la misma universidad en cotutela con la Ecole Normale Supérieure de Lyon (Francia) bajo la dirección de los profesores Eric Goles y Jacques Mazoyer. En el marco de la cotutela hice dos estadías en Francia de 6 y 12 meses respectivamente. Defendí la tesis el 1 de junio de 2001. Luego hice un post-doctorado en la l'Université Catholique de Louvain (Bélgica), bajo la dirección del profesor Vincent Blondel.
 
Proyectos
Docencia
Estudiantes




 

Difusión

Láminas sobre optimización combinatorial, criptografía y teselados.

 

Publicaciones

Universal cellular automaton over a hexagonal tiling with 3 states, A. Gajardo, E. Goles; International Journal of Algebra and Computation, 11 (3), pp 335-354, (2001)
Complexity of Langton's ant, A. Gajardo, A. Moreira, E. Goles; Discrete Applied Mathematics, 117, pp 41-50, (2002) (+)
Dynamical behavior and complexity of Langton's ant, A. Moreira, A.Gajardo, E. Goles; Complexity, 6 (4), pp 46-52, (2000) (+)
Generalized Langton's ant: dynamical behavior and complexity, A. Gajardo, A. Moreira, E. Goles; STACS 2001, Lecture Notes in Computer Science N. 2010, pp 259-270, (2001) (+)
A symbolic projection of langton's Ant (Extended Abstract), A. Gajardo; DM-CS 2003, AB, pp. 57-68, Discrete Mathematics and Theoretical Computer Science, (2003).
Dynamics of a class of ants on a one-dimensional lattice, A. Gajardo, E. Goles; Theor. Comput. Sci., 322(2), pp 267-283, (2004).
A measure of similarity between graph vertices: applications to synonym extraction and web searching, V. D. Blondel, A. Gajardo, M. Heymans, P. Senellart, P. Van Dooren, SIAM Review, 46 (4), pp 647-666, (2004).
Crossing information in two dimensional Sandpiles, A. Gajardo, E. Goles; Theor. Comput. Sci., 369(1-3), pp 463-469 (2006).
One head machines from a symbolic approach, A. Gajardo, J. Mazoyer; Theor. Comput. Sci., 370, pp 34-47 (2007).
Circuit Universality of two dimensional cellular automata: a review, A. Gajardo, E. Goles; in Randomness and complexity, from Leibniz to Chaitin, editado por Cristian Calude, World Scientific Pub., 2007.
On the complexity of feedback set problems in signed digraphs, M. Montalva, J. Aracena, A. Gajardo; Electronic Notes in Discrete Mathematics, 30, pp 249-254 (2008).
Sofic one head machines, A. Gajardo; (JAC 2008), Uzes, Francia.
Langton's flies, P. Dorbec, A. Gajardo; J. Phys. A: Math. Theor., 41 (2008) 405101.
Zigzags in Turing Machines, A. Gajardo, P. Guillon; (CSR 2010) Kazán, Rusia. Lecture Notes in Computer Science N. 6072, pp 109-119 (2010)
Time-symmetric cellular automata, A. Moreira, A. Gajardo; (JAC 2010), Turku, Finlandia.
On time-symmetry in cellular automata, A. Gajardo, J. Kari, A. Moreira; J. of Comput. Syst. Sci., 78 (4), pp 1115-1126 (2012).
Cellular Automata Model for the Urban Growth of the Metropolitan Area of Concepcion (CAMAC), D. Maldonado, A. Gajardo, C. Rojas, P. Valdebenito, C. Cantergiani; (CAMUSS 2012), Oporto, Portugal.
Undecidability of the surjectivity of the subshift associated to a Turing machine, R. Torres, N. Ollinger, A. Gajardo; (RC 2012) Copenhague, Dinamarca. Lecture Notes in Computer Science N. 7581, pp 44-56 (2012).
Revisiting of 2-pebble automata from a dynamical approach, A. Gajardo, C. Lacalle; Pre-print DIM 2014-08 (2014).
Some undecidable problems about the trace-subshift associated to a Turing machine, A. Gajardo, N. Ollinger, R. Torres-Avilés; Discrete Mathematics & Theoretical Computer Science, 17(2), pp 267-284 (2015).
Universal Time-Symmetric Number-Conserving Cellular Automaton, D. Maldonado, A. Moreira, A. Gajardo; (AUTOMATA 2015) Turku, Finlandia. Lecture Notes in Computer Science N. 9099, pp 155-168 (2015)
The transitivity problem of Turing machines, A. Gajardo, N. Ollinger, R. Torres-Avilés; (MFCS 2015) Milan, Italia. Lecture Notes in Computer Science N. 9234 (2015)
Pre-expansivity in cellular automata, A. Gajardo, V. Nesme, G. Theyssier; Pre-print DIM 2016-03 (2016).
Non trivial Turmites are Turing-universal, A. Gajardo, B. Hellouin de Menibus, D. Maldonado, A. Moreira; Pre-print DIM 2016-09 (2016).

Tesis

Memoria de ingeniería, (1998): Autómatas celulares universales en 2 dimensiones, con vecindades de tamaño 3 y 4
Tesis de doctorado, (2001): Influencia de la red espacial en el comportamiento de un sistema dinámico: la hormiga de Langton, (resumen, texto completo .ps.gz)

Proyectos

The dynamics of Turing Machines and similar systems. FONDECYT # 1030706, de 2003 a 2005.
Dynamics of one head machines and t-shifts. FONDECYT # 1061036, de 2006 a 2008.
One head machines and their associated symbolic systems. FONDECYT # 1090568, de 2009 a 2011.
Number conserving cellular automata: theory and applications. ECOS-CONICYT # C12E05, de 2013 a 2015.
On the complexity of one head machines on Cayley graphs. FONDECYT # 1140684, de 2014 a 2016.
Reversibility and Time-symmetry in Conservative and General Cellular Automata. FONDECYT # 1140833, de 2014 a 2015 (colaborador).

Docencia

Cursos dictados: Álgebra IV: Introducción a la matemática discreta (525412), Álgebra y álgebra lineal (520142), Álgebra II (525148) Álgebra III (525201), Álgebra (525103), Matemática I (529103), Matemática II (529104), Matemáticas Universales (522236), Optimización III (525551), Teoría de Grafos (4220005), Autómatas Celulares (525555), Complejidad Algorítmica (4220006), Sistemas Dinámicos Discretos (525612), Optimización I (525351).

Estudiantes

Paul Dorbec: Practicante de Magister, Ecole Normale Supérieure de Lyon, Francia, desde el 4 de junio al 4 de agosto de 2003.
Marco Montalva: Memorista de Ingeniería Civil Matemática, Universidad de Concepción, Chile, desde marzo de 2005 a mayo de 2006.
Bruno Karelovic: Memorista de Ingeniería Civil Matemática, Universidad de Concepción, Chile, desde agosto de 2009 a abril de 2010.
Camilo Lacalle: Memorista de Ingeniería Matemática, Universidad de Concepción, Chile, desde septiembre de 2010 a marzo de 2012.
Rodrigo Torres: Estudiante de Doctorado en Ciencias Aplicadas, Universidad de Concepción, Chile, de mayo de 2012 a enero 2016.
Diego Maldonado: Estudiante de Ingeniería Civil Matemática, Universidad de Concepción, Chile, de mayo de 2014 a septiembre 2015.