=ADD=
=reftype=
14
=number=
93-46
=year=
1993
=author=
Sutner; Klaus
=title=
Linear Cellular Automata and their Fischer Automata
=month=
08
=keywords=
automata theory
=abstract=
We construct a class of binary linear cellular
automata whose corresponding minimal automata
exhibit exponential blow-up. The automata have
Hamming distance 1 to a bideterministic automaton.
Moreover, the equivalent minimal Fischer automata
are obtained from the minimal automata by deleting
the sink and therefore have a maximal complexity.