Invertible linear automata
Linear cellular automataLinear cellular automata are those automata whose dependency on neighbouring cells is always via
Linear cellular automata are a subset of linear finite state machines - for which there are a number of existing theoretical results of relevance to invertability.
Modelling the transition function with a matrixSince the contributions from dependent cells can be simply added together, the transition function of linear finite state machines may be expressed as a matrix,
The current state is represented by a vector. To
perform the transition function, the current state is
multiplied by the matrix, and then the fixed vector,
ResultsIf the matrix is non-singular - i.e. it has a non-zero determinant, then the corresponding FSM is invertible. This fact results in a relatively simple test for reversibility - and in a concrete method for constructing the inverse of the transition rule of a given FSM.
There is a "primitive polynomial" corresponding to the
transition function, whose coefficients may be found by
If this polynomial is primitive, then the
whole FSM will exhibit behaviour with a period equal to
NotesVery frequently, the inverse of a linear cellular automaton is found to require a much larger neighbourhood than the original automaton.
It has been proven that every maximal-period linear FSM with a single output has an exact equivalent in the form of some maximal-period LFSR.