On the complexity of generalized Q2R automaton

DOI10.1016/j.aam.2022.102355OpenAlexW3190264350MaRDI QIDQ2134005

Martín Ríos-Wilson, Pedro Montealegre, Marco Montalva-Medel, Eric Goles Chacc

Publication date: 5 May 2022

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.03335

zbMATH Keywords

computational complexitylimit cyclesP-completenessQ2R networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relaxation properties of elementary reversible cellular automata
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• No polynomial bound for the period of the parallel chip firing game on graphs
• Phase space classification of an Ising cellular automaton: the Q2R model
• Invariant in cellular automata
• Beitrag zur Theorie des Ferromagnetismus

This page was built for publication: On the complexity of generalized Q2R automaton