Complexity classes on spatially periodic cellular automata

DOI10.4230/LIPICS.STACS.2014.112MaRDI QIDQ2965477zbMATH OpenOpenAlexFDO

Authors Nicolas Bacquey

Publication date 3 March 2017

Full work available at URL https://hal.science/hal-00957130

zbMATH Keywords

linear spacedensity classificationpolynomial timecomputable functionslanguage recognitioncyclic languagesalgorithms on cellular automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cellular automata (computational aspects) (68Q80)

Recommendations

• scientific article; zbMATH DE number 17562
• Periodic orbits for additive cellular automata
• Classifying circular cellular automata
• scientific article; zbMATH DE number 2113941
• Computational classification of cellular automata

Cited in

(6)

• Complexity-theoretic aspects of expanding cellular automata
• Leader election on two-dimensional periodic cellular automata
• A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes
• scientific article; zbMATH DE number 1462667 (Why is no real title available?)
• A portfolio of classification problems by one-dimensional cellular automata, over cyclic binary configurations and parallel update
• Complexity-theoretic aspects of expanding cellular automata

This page was built for publication: Complexity classes on spatially periodic cellular automata

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