Solving the parity problem in one-dimensional cellular automata

DOI10.1007/s11047-013-9374-9zbMath1334.68140arXiv1208.2758OpenAlexW2076251080MaRDI QIDQ272769

Pedro P. B. de Oliveira, Heather Betel, Paola Flocchini

Publication date: 21 April 2016

Published in: Natural Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.2758

zbMATH Keywords

de Bruijn graphsdensity classificationelementary cellular automataemergent computationparity problem

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items (10)

A portfolio of classification problems by one-dimensional cellular automata, over cyclic binary configurations and parallel update ⋮ Synchronous solution of the parity problem on cyclic configurations, with elementary cellular automaton rule 150, over a family of directed, non-circulant, regular graphs ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Inversion of Mutually Orthogonal Cellular Automata ⋮ Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models ⋮ Unnamed Item ⋮ Shift-equivalence of \(k\)-ary, one-dimensional cellular automata rules ⋮ A perfect solution to the parity problem with elementary cellular automaton 150 under asynchronous update ⋮ Characterisation of the elementary cellular automata with neighbourhood priority based deterministic updates ⋮ A fully operational framework for handling cellular automata templates

Cites Work

• On the relationship between fuzzy and Boolean cellular automata
• Conservation of some dynamical properties for operations on cellular automata
• On the directional dynamics of additive cellular automata
• Solution of some conjectures about topological properties of linear cellular automata
• The computational power of population protocols
• Improvement of a Result on Sequencing Elementary Cellular Automata Rules for Solving the Parity Problem
• Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
• Distributed Computing: A Locality-Sensitive Approach
• Additive Cellular Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving the parity problem in one-dimensional cellular automata