Computational complexity of the stability problem for elementary cellular automata

MaRDI QIDQ5010393zbMATH OpenFDO

Authors Fabiola Lobos, Pedro Montealegre, Eurico L. P. Ruivo, Pedro P. B. de Oliveira, Eric Goles

Publication date 25 August 2021

Full work available at URL https://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-15-number-4-2020/jca-15-4-p-261-304/

zbMATH Keywords

computational complexitystability problemelementary cellular automatadecision problemone-dimensional cellular automata

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of the stability problem of binary freezing totalistic cellular automata
• scientific article; zbMATH DE number 17562
• On the computational complexity of finite cellular automata
• Evolution complexity of the elementary cellular automaton rule 18
• Cellular automata: descriptional complexity and decidability

Cites work

• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• scientific article; zbMATH DE number 3896307 (Why is no real title available?)
• scientific article; zbMATH DE number 3898249 (Why is no real title available?)
• scientific article; zbMATH DE number 3898250 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Cellular automata and communication complexity
• Classes of linear automata
• Communication complexity and intrinsic universality in cellular automata
• Communication complexity in number-conserving and monotone cellular automata
• Majority-vote cellular automata, Ising dynamics, and P-completeness
• On density determination with cellular automata: results, constructions and directions
• P-completeness of Cellular Automaton Rule 110
• Traced communication complexity of cellular automata
• Universality in elementary cellular automata

Cited in

(4)

• Complexity analysis of time series generated by elementary cellular automata
• On the complexity of the stability problem of binary freezing totalistic cellular automata
• Amoebae for clustering: a bio-inspired cellular automata method for data classification
• Computational complexity of dynamical systems: the case of cellular automata

This page was built for publication: Computational complexity of the stability problem for elementary cellular automata

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