Search

The parity problem is one of the classical benchmarks for probing the computational ability of cellular automata. It refers to conceiving a rule to allow deciding whether the number of 1s in an arbitrary binary sequence is an odd or even number, without resorting to globally accessing the sequence. In its most traditional formulation, it refers to cyclic configurations of odd length, which, under the action of a cellular automaton, should converge to a fixed point of all cells in the 0-state, if the configuration initially has an even number of 1s, or to a fixed point of all cells in the 1-state, otherwise. It has been shown that the problem can be solved in this formulation, in particular by a rule alone. Here, we provide a synchronous solution to the problem, by relying upon elementary cellular automaton rule 150, the elementary local parity rule, over a connection pattern among the cells defined by a family of directed, non-circulant, regular graphs. This represents the simplest synchronous solution currently known for cyclic configurations and, quite interestingly, being an instance of the solution of a non-trivial global problem by means of its local counterpart. [ABSTRACT FROM AUTHOR]

The parity problem is a classical binary benchmark for addressing the computational ability and limitations of automata networks. It refers to conceiving a local rule to allow deciding whether the number of 1-states in the nodes of an arbitrary network is an odd or even number, without global access to the nodes. In its standard formulation, the automata network has an odd number of nodes whose states, arranged as a cyclic configuration, should converge to a fixed point of all 0s, if the initial configuration has an even number of 1s, or to a fixed point of all 1s, otherwise. It has been shown that a local rule alone is able to solve the problem in this formulation, including a synchronous solution we have recently shown, totally based on the local parity rule of the cellular automata elementary space (number 150), with a certain pattern of connection between the nodes. Here, we generalise this solution, showing how to construct many others, combining rule 150 with rules 170 and 240, which are the local shifts of the same space, in such a way that the original solution is just one among countless possibilities. Such solutions may have different convergence times for specific configurations, but are equivalent in the context of all configurations of a given size; also, various solutions form symmetric pairs, in terms of the actual rules they used. The solutions were evaluated computationally and presented here without their formal proofs, but empirical evidences strongly suggest that they can be obtained by the same kind of technique we used in the solution exclusively with rule 150. • Extensive studies have been carried out addressing the ability of cellular automata to solve (or not) computational problems by distributed consensus, i.e., to solve global problems on their lattice, with all cells reaching a homogeneous fixed point, by totally local action. • The problem we address – the parity problem – is a key instance in the class, which has been studied as a benchmark problem for already several decades in computer science in general. Our stance is to solve it not over the standard grid type connection pattern of the units that define cellular automata, but in the more flexible graph type connection pattern of automata networks. • Recently, we managed to solve the problem with a single local rule but we later found out that this result was just one instance of a much bigger family of solutions, now employing two additional local rules; this is exactly what we reported in the manuscript, with a focus on how to construct these solutions and some analyses of their relative efficiencies. • The richness of solutions we presented reinforce the power of arbitrary automata networks over the rigidity of circulant type connection patterns that characterise standard cellular automata. [ABSTRACT FROM AUTHOR]

Abstract: Generalized recoupling coefficients or -coefficients can be expressed as multiple sums over products of Racah or 6j-coefficients [L.C. Biedenharn, J.D. Louck, Coupling of n angular momenta: recoupling theory, in: The Racah–Wigner Algebra in Quantum Theory, Encyclopedia of Mathematics and its Applications, vol. 9, Addison-Wesley, 1981, pp. 435–481]. The problem of finding an optimal summation formula (i.e. with a minimal number of Racah coefficients) for a given -coefficient is equivalent to finding an optimal reduction of a so-called Yutsis graph [A.P. Yutsis, I.B. Levinson, V.V. Vanagas, Mathematical Apparatus of the Theory of Angular Momentum, Israel Program for Scientific Translation, Jerusalem, 1962]. In terms of graph theory Yutsis graphs are connected simple cubic graphs which can be partitioned into two vertex induced trees. The two parts are necessarily of the same size. In this area Yutsis graphs are also studied under the name of cubic dual Hamiltonian graphs [F. Jaeger, On vertex-induced forests in cubic graphs, in: Proc. 5th Southeastern Conference, Congr. Numer. (1974) 501–512]. We present algorithms for determining whether a cubic graph is a Yutsis graph. This is interesting for generating large test cases for programs (as in [P.M. Lima, Comput. Phys. Comm. 66 (1991) 89; S. Fritzsche, T. Inghoff, T. Bastug, M. Tomaselli, Comput. Phys. Comm. 139 (2001) 314; D. Van Dyck, V. Fack, GYutsis: heuristic based calculation of general recoupling coefficients, Comput. Phys. Comm. 154 (2003) 219–232]) that determine a summation formula for a -coefficient. Moreover, we give the numbers of Yutsis and non-Yutsis cubic graphs with up to 30 vertices and cubic polyhedra with up to 40 vertices. All these numbers have been computed by two independent programs in order to reduce the probability of error. Since the decision problem whether a given cubic graph is Yutsis or not is NP-complete, we could not hope for a polynomial time worst case performance of our programs. Nevertheless the programs described in this article are very fast on average. [Copyright &y& Elsevier]