4 papers
Non-trivial automata networks do exist that solve the global majority problem with the local majority rule
Pedro Paulo Balbi, Kévin Perrot, Marius Rolland +1
The global majority problem, often referred to as the Density Classification Task, is a classical benchmark in the context of probing the computational capabilities of automata net…
Cellular automata can really solve the parity problem
Barbara Wolnik, Anna Nenca, Pedro Paulo Balbi +1
Determining properties of an arbitrary binary sequence is a challenging task if only local processing is allowed. Among these properties, the determination of the parity of 1s by d…
Solving decision problems by distributed consensus with one-dimensional, binary, radius- cellular automata over cyclic configurations
Eurico Ruivo, Pedro Paulo Balbi, Kévin Perrot +2
Probing the ability of automata networks to solve decision problems has received a continuous attention in the literature, and specially with the automata reaching the answer by di…
Unitary Quantum Cellular Automata for Density Classification
Pedro C. S. Costa, Yuval R. Sanders, Pedro Paulo Balbi +1
We investigate the density classification task (DCT) -- determining the majority bit in a one-dimensional binary lattice -- within a quantum cellular automaton (CA) framework. Whil…