SYNTHESIS OF ONE-DIMENSIONAL LINEAR HYBRID CELLULAR-AUTOMATA

This paper presents a method for the synthesis of a one-dimensional li near hybrid cellular automaton (CA) from a given irreducible polynomia l, A detailed description of the algorithm is given, together with an outline of the theoretical background, It is shown that two CA exist f or each irreducible polynomial, solving the previously open CA existen ce conjecture. An in-depth example of the synthesis is presented, alon g with timing benchmarks and an operation count, The algorithm solves the previously open problem of synthesizing CA for all practical appli cations.