Intrinsic universality in automata networks I: Families and simulations
M. Ríos Wilson, G. Theyssier
Theoretical Computer Science (38p.) doi:10.1016/j.tcs.2024.114511
Full paper
On the parameterized complexity of freezing dynamics
E. Goles, P. Montealegre, M. Ríos Wilson, G. Theyssier
Advances in Applied Mathematics (29p.) doi:10.1016/j.aam.2024.102706
Full paper
Local Certification of Majority Dynamics
D. Maldonado, P. Montealegre, M. Ríos Wilson, G. Theyssier
SOFSEM 2024 (24p.) doi:10.1007/978-3-031-52113-3_26
Full paper
On the Dynamics of Bounded-Degree Automata Networks
J. Aracena, F. Bridoux, P. Guillon, K. Perrot, A. Richard, G. Theyssier
Exploratory paper AUTOMATA 2023 (22p.) doi:10.5281/zenodo.8276252
Full paper
On the complexity of freezing automata networks of bounded pathwidth
E. Goles, P. Montealegre, M. Ríos Wilson, G. Theyssier
Exploratory paper AUTOMATA 2023 (22p.) doi:10.5281/zenodo.8276242
Full paper
On Turedo Hierarchies and Intrinsic Universality
S. Nalin, G. Theyssier
DNA 2022 (18p.) doi:10.4230/LIPIcs.DNA.28.6
Full paper
Cold dynamics in cellular automata: a tutorial
G. Theyssier
Natural Computing (25p.) doi:10.1007/s11047-022-09886-2
Full paper
Cellular automata and bootstrap percolation
V. Salo, G. Theyssier, I. Törmä
Theoretical Computer Science (12p.) doi:10.1016/j.tcs.2022.04.015
Full paper
The Mirage of Universality in Cellular Automata
G. Theyssier
Book chapter (13p.) doi:10.1007/978-3-030-92551-2_5
Full paper
Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)
D. Pchelina, N. Schabanel, S. Seki, G. Theyssier
STACS 2022 (23p.) doi:10.4230/LIPIcs.STACS.2022.51
Full paper
Freezing, Bounded-Change and Convergent Cellular Automata
N. Ollinger, G. Theyssier
Discrete Mathematics & Theoretical Computer Science (37p.) doi:10.46298/dmtcs.5734
Full paper
On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics
E. Goles, P. Montealegre, M. Ríos Wilson, G. Theyssier
CiE 2021 (29p.) doi:10.1007/978-3-030-80049-9_24
Full paper
Rice-Like Theorems for Automata Networks
G. Gamard, P. Guillon, K. Perrot, G. Theyssier
STACS 2021 (17p.) doi:10.4230/LIPIcs.STACS.2021.32
Full paper
Commutative Automata Networks
F. Bridoux, M. Gadouleau, G. Theyssier
AUTOMATA 2020 (15p.) doi:10.1007/978-3-030-61588-8_4
Full paper
On Simulation in Automata Networks
F. Bridoux, M. Gadouleau, G. Theyssier
CiE 2020 (19p.) doi:10.1007/978-3-030-51466-2_24
Full paper
Expansive Automata Networks
F. Bridoux, M. Gadouleau, G. Theyssier
Theoretical Computer Science (19p.) doi:10.1016/j.tcs.2020.06.019
Full paper
Pre-expansivity in cellular automata
A. Gajardo, V. Nesme, G. Theyssier
Theoretical Computer Science (47p.) doi:10.1016/j.tcs.2019.10.034
Full paper
Characterizing asymptotic randomization in abelian cellular automata
B. Hellouin de Menibus, V. Salo, G. Theyssier
Ergodic Theory and Dynamical Systems (21p.) doi:10.1017/etds.2018.75
Full paper
Universality in Freezing Cellular Automata
F. Becker, D. Maldonado, N. Ollinger, G. Theyssier
CiE 2018 (21p.) doi:10.1007/978-3-319-94418-0_5
Full paper
On the complexity of two-dimensional signed majority cellular automata
E. Goles, P. Montealegre, K. Perrot, G. Theyssier
Journal of Computer and System Sciences (32p.) doi:10.1016/j.jcss.2017.07.010
Full paper
On the Cost of Simulating a Parallel Boolean Automata Network by a Block-Sequential One
F. Bridoux, P. Guillon, K. Perrot, S. Sené, G. Theyssier
TAMC 2017 (19p.) doi:10.1007/978-3-319-55911-7_9
Full paper
Propagation, Diffusion and Randomization in Cellular Automata
G. Theyssier
Long abstract of invited talk AUTOMATA 2016 (7p.) doi:10.1007/978-3-319-39300-1_1
Full paper
μ-Limit sets of cellular automata from a computational complexity perspective
L. Boyer, M. Delacourt, V. Poupet, M. Sablik, G. Theyssier
Journal of Computer and System Sciences (41p.) doi:10.1016/j.jcss.2015.05.004
Full paper
Introducing Freezing Cellular Automata
E. Goles, N. Ollinger, G. Theyssier
Exploratory paper AUTOMATA 2015 (10p.) doi:NO DOI
Full paper
Strict Majority Bootstrap Percolation in the r-wheel
M. A. Kiwi, P. Moisset de Espanés, I. Rapaport, S. Rica, G. Theyssier
Information Processing Letters (12p.) doi:10.1016/j.ipl.2014.01.005
Full paper
Intrinsic universality in tile self-assembly requires cooperation
P.-E. Meunier, M. J. Patitz, S. M. Summers, G. Theyssier, A. Winslow, D. Woods
SODA 2014 (43p.) doi:10.1137/1.9781611973402.56
Full paper
Stochastic Cellular Automata: Correlations, Decidability and Simulations
P. Arrighi, N. Schabanel, G. Theyssier
Fundamentae Informaticae (35p.) doi:10.3233/FI-2013-875
Full paper
Asymptotically almost all lambda-terms are strongly normalizing
R. David, C. Raffali, K. Grygiel, J. Kozik, G. Theyssier, M. Zaionc
Logical Methods in Computer Science (38p.) doi:10.2168/LMCS-9(1:2)2013
Full paper
Subshifts as models for MSO logic
E. Jeandel, G. Theyssier
Information and Computation (17p.) doi:10.1016/j.ic.2013.01.003
Full paper
Intrinsic Simulations between Stochastic Cellular Automata
P. Arrighi, N. Schabanel, G. Theyssier
JAC 2012 (17p.) doi:10.4204/EPTCS.90.17
Full paper
Selfsimilarity, Simulation and Spacetime Symmetries
V. Nesme, G. Theyssier
AUTOMATA 2011 (20p.)
Full paper
Clandestine Simulations in Cellular Automata
P. Guillon, P.-E. Meunier, G. Theyssier
JAC 2010 (18p.)
Full paper
Bulking II: Classifications of Cellular Automata
M. Delorme, J. Mazoyer, N. Ollinger, G. Theyssier
Theoretical Computer Science (42p.) doi:10.1016/j.tcs.2011.02.024
Full paper
Bulking I: an Abstract Theory of Bulking
M. Delorme, J. Mazoyer, N. Ollinger, G. Theyssier
Theoretical Computer Science (27p.) doi:10.1016/j.tcs.2011.02.023
Full paper
Directional Dynamics along Arbitrary Curves in Cellular Automata
M. Delacourt, V. Poupet, M. Sablik, G. Theyssier
Theoretical Computer Science (37p.) doi:10.1016/j.tcs.2011.02.019
Full paper
Communication Complexity and Intrinsic Universality in Cellular Automata
E. Goles, P.-E. Meunier, I. Rapaport, G. Theyssier
Theoretical Computer Science (32p.) doi:10.1016/j.tcs.2010.10.005
Full paperErratum
On Factor Universality in Symbolic Spaces
L. Boyer, G. Theyssier
MFCS 2010 (15p.) doi:10.1007/978-3-642-15155-2_20
Full paper
Topological Dynamics of Cellular Automata: Dimension Matters
M. Sablik, G. Theyssier
Theory of Computing Systems (23p.) doi:10.1007/s00224-010-9255-x
Full paper
Subshifts, Languages and Logic
E. Jeandel, G. Theyssier
DLT 2009 (16p.) doi:10.1007/978-3-642-02737-6_23
Full paper
On Local Symmetries and Universality in Cellular Automata.
L. Boyer, G. Theyssier
STACS 2009 (12p.) doi:10.4230/LIPIcs.STACS.2009.1836
Full paper
Amalgamation of Cellular Automata.
G. Theyssier
JAC 2008
Full paperErratum
Topological Dynamics of 2D Cellular Automata.
M. Sablik, G. Theyssier
CiE 2008 (13p.) doi:10.1007/978-3-540-69407-6_56
Full paper
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures.
L. Boyer, V. Poupet, G. Theyssier
MFCS 2006 (13p.) doi:10.1007/11821069_17
Full paper
How common can be universality in cellular automata?
G. Theyssier
STACS 2005 doi:10.1007/978-3-540-31856-9_10
Full paper
Captive Cellular Automata.
G. Theyssier
MFCS 2004 doi:10.1007/978-3-540-28629-5_32
Full paper
Cellular automata and communication complexity.
C. Dürr, I. Rapaport, G. Theyssier
Theoretical Computer Science doi:10.1016/j.tcs.2004.03.017
Full paper
HomePapersTalksPhd thesisListsThemesCAStudentsImagesACMLPop-scienceOpen/free
Français
English
Español
Home
Publications
Research
Others