Abstract 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 distributed consensus has been a recurring endeavour in the context of automata networks. In its most standard formulation, a one-dimensional cellular automaton rule should process any odd-sized cyclic configuration and lead the lattice to converge to the homogeneous fixed point of 0s if the parity of 1s is even and to the homogeneous fixed point of 1s, otherwise. The only proposed solution to this problem with a single rule was given more than 10 years ago (and coined BFO rule after the authors’ initials). However, three years later its authors realised that the rule would fail for a specific configuration and proposed a computationally sound fix, but a proof could not be worked out. Here we provide a fix to that failing rule along with a full proof, therefore reassuring that a single-rule solution to the problem really does exist.

The parity problem is one of the best-known classification problems studied to examine the computational abilities of cellular automata . In this inverse problem , one is looking for a cellular automaton that can classify each initial configuration into one of two classes according to its parity. In the case of deterministic one-dimensional cellular automata , there exists a local rule that effectively solves the parity problem, but it is unknown whether it is the simplest possible rule. Specifically, it is known that a cellular automaton with a nine-cell neighborhood can solve the parity problem, whereas no cellular automaton with a five-cell neighborhood is capable of doing so. These findings have remained unimproved for the past 10 years. In this paper, we present novel tools that allow to narrow down the existing gap. With the help of these tools, we are able to demonstrate that there is no cellular automaton with a six-cell neighborhood capable of solving the parity problem.

A signed graph is a pair (G,σ), where G=(V(G),E(G)) is an undirected graph and σ:E(G)→{+,−} is a function which marks each edge with “+” or “−”. Two signed graphs are equivalent if one of them can be changed to the other by a sequence of resigning operations. The single resigning operation chooses a vertex v∈V(G) and flips the signs of all edges incident to v. By [G,σ] we shall denote the equivalence class of the signed graph (G,σ). Each element of [G,σ] is called a presentation of [G,σ]. In this paper we shall call both (G,σ) and [G,σ] signed graphs. The coloring of signed graphs is defined through homomorphism. The signed graph [G,σ] is colored by the signed graph (G2,σ2), if there exists a presentation (G,σ1) of [G,σ] and a vertex-mapping ϕ from G to G2 which preserves signs of the edges. In this paper we show that: (a) The signed chromatic number for the class G of all 2-dimensional grids lies between 5 and 6. (b) Every signed grid with at most seven rows can be colored with five colors. (c) Every signed grid with two rows can be colored with four colors.