On the complexity of generalized Q2R automaton

DOI10.1016/J.AAM.2022.102355MaRDI QIDQ2134005zbMATH OpenOpenAlexFDO

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

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) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Recommendations

• PSPACE-completeness of majority automata networks
• Computational complexity of threshold automata networks under different updating schemes
• Generalized Automata Networks
• Phase space classification of an Ising cellular automaton: the Q2R model
• On the computational complexity of finite cellular automata

Cites work

• scientific article; zbMATH DE number 3898249 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Beitrag zur Theorie des Ferromagnetismus
• Invariant in cellular automata
• Majority-vote cellular automata, Ising dynamics, and 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
• Relaxation properties of elementary reversible cellular automata

Cited in

(2)

• On the Complexity of Equivalence and Minimisation for Q-weighted Automata
• Intrinsic universality in automata networks. II: Glueing and gadgets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2134005)