Cover Image

Descriptive Complexity of Sensitivity of Cellular Automata

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Favereau, Tom, Salo, Ville
Format:	Preprint
Published:	2025
Subjects:	Dynamical Systems Computational Complexity Logic 37B15 (Primary), 68Q80 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Extended Cellular Automata
by: Mehdipour, Pouya, et al.
Published: (2025)

Structure and computability of preimages in the Game of Life
by: Salo, Ville, et al.
Published: (2023)

The Self-Replication Phase Diagram: Mapping Where Life Becomes Possible in Cellular Automata Rule Space
by: Yin, Don
Published: (2026)

2D Moore CA with new boundary conditions and its reversibility
by: Omirov, B. A., et al.
Published: (2024)

Weighted Automata and Logics Meet Computational Complexity
by: Kostolányi, Peter
Published: (2023)

On the Dynamical Hierarchy in Gathering Protocols with Circulant Topologies
by: Gerlach, Raphael, et al.
Published: (2023)

Quasi-fixed points of substitutive systems
by: Krawczyk, Elżbieta
Published: (2024)

Symbol Frequencies in Surjective Cellular Automata
by: de Menibus, Benjamin Hellouin, et al.
Published: (2025)

Solving the initial value problem for cellular automata by pattern decomposition
by: Fukś, Henryk
Published: (2025)

No weakly factor-universal cellular automaton
by: Gwozdz, Maja
Published: (2026)

Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models
by: Gayral, Léo, et al.
Published: (2023)

On the algorithmic descriptive complexity of attractors in topological dynamics
by: Rojas, Cristobal, et al.
Published: (2023)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

A Minimal Substitution Basis for the Kalmár Elementary Functions
by: Prunescu, Mihai, et al.
Published: (2025)

Almost automorphic subshifts with finiteness conditions for the boundary of the separating cover
by: Sell, Daniel, et al.
Published: (2024)

A Formalization of Abstract Rewriting in Agda
by: Arkle, Sam, et al.
Published: (2026)

Computable thermodynamic formalism
by: Binder, Ilia, et al.
Published: (2025)

Automaticity of uniformly recurrent substitutive sequences
by: Krawczyk, Elżbieta, et al.
Published: (2021)

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

Edit distance in substitution systems
by: Best, Andrew, et al.
Published: (2024)

Computational Complexity of Model-Checking Quantum Pushdown Systems
by: Lin, Deren, et al.
Published: (2025)

Parametrized complexity of relations between multidimensional subshifts
by: Carrasco-Vargas, Nicanor, et al.
Published: (2025)

Expansive actions with specification on uniform spaces, topological entropy, and the Myhill property
by: Ceccherini-Silberstein, Tullio, et al.
Published: (2019)

Dumont-Thomas complement numeration systems for $\mathbb{Z}$
by: Labbé, Sébastien, et al.
Published: (2023)

Density of group languages in shift spaces
by: Berthé, Valérie, et al.
Published: (2024)

Decidability of the isomorphism problem between multidimensional substitutive subshifts
by: Cabezas, Christopher, et al.
Published: (2024)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Stable finiteness of monoid algebras and surjunctivity
by: Ceccherini-Silberstein, Tullio, et al.
Published: (2024)

On linear shifts of finite type and their endomorphisms
by: Ceccherini-Silberstein, Tullio, et al.
Published: (2020)

Multidimensional tilings and MSO logic
by: Pallen, Rémi, et al.
Published: (2025)

On injective endomorphisms of symbolic schemes
by: Ceccherini-Silberstein, Tullio, et al.
Published: (2017)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Thermodynamic Formalism for a family of cellular automata and duality with the shift
by: Lopes, Artur O., et al.
Published: (2024)

Thermodynamic formalism of countably generated self-affine sets
by: Käenmäki, Antti, et al.
Published: (2024)

Projectivity in topological dynamics
by: Bal, Jashan
Published: (2025)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
by: Kattermann, David, et al.
Published: (2025)

Eventual Conjugacy of Free Inert $G$-SFTs
by: Epperlein, Jeremias
Published: (2023)

On the minimal memory set of cellular automata
by: Castillo-Ramirez, Alonso, et al.
Published: (2024)

One-dimensional cellular automata with a unique active transition
by: Castillo-Ramirez, Alonso, et al.
Published: (2024)