Name
Abstract | ||
|---|---|---|
We study the sizes of minimal finite state machines associated with linear cellular automata. In particular, we construct a class of binary linear cellular automata whose corresponding minimal automata exhibit full exponential blow-up. These cellular automata have Hamming distance 1 to a permutation automaton. Moreover, the corresponding minimal Fischer automata as well as the minimal DFAs have maximal complexity. By contrast, the complexity of higher iterates of a cellular automaton always stays below the theoretical upper bound. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0167-8191(97)00080-X | Parallel Computing |
Keywords | Field | DocType |
linear cellular automaton,cellular automata,minimal automata,permutation automata,fischer automaton,hamming distance,finite state machine,cellular automaton,upper bound | Discrete mathematics,Cellular automaton,Quantum finite automata,Combinatorics,Continuous spatial automaton,Mobile automaton,Computer science,Reversible cellular automaton,Timed automaton,Stochastic cellular automaton,ω-automaton | Journal |
Volume | Issue | ISSN |
23 | 11 | Parallel Computing |
Citations | PageRank | References |
10 | 1.16 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Klaus Sutner | 1 | 119 | 19.42 |