THE SET OF REVERSIBLE 90 150-CELLULAR-AUTOMATA IS REGULAR/

The reversibility problem for 90/150 cellular automata (both null and periodic boundary) is tackled using continuants and regular expression s. A 90/150 cellular automata can be uniquely encoded by a string over the alphabet {0, 1}. It is shown that the set of strings which corres pond to reversible 90/150 cellular automats is a regular set. We use t he regular expression to enumerate the number of reversible strings of a fixed length. As a consequence, it is shown that given a polynomial p(x), it is not always possible to get a 90/150 cellular automata who se transition matrix has characteristic polynomial p(x). (C) 1998 Else vier Science B.V. All rights reserved.