Complexity classes on spatially periodic Cellular Automata

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

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)

Cited In (4)

• 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

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)