Complexity classes on spatially periodic cellular automata

DOI10.4230/LIPICS.STACS.2014.112zbMATH Open1359.68204OpenAlexW2247407080MaRDI QIDQ2965477FDOQ2965477

Authors: Nicolas Bacquey 

Publication date: 3 March 2017

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

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

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)

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
• Title not available (Why is that?)
• 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)