Generation by lazy and invertible cellular automata over the Klein four-group
En palabras de los autores
Let and . We characterize the submonoid of generated by lazy and invertible cellular automata. A cellular automaton belongs to this submonoid if and only if, whenever it maps the two free -orbits onto the same free orbit, it maps both constant configurations and some two-point orbit to the same constant. The proof gives a factorization using elementary orbit collapses and three two-cell lazy maps. The criterion yields the cardinality and identifies the maps missed by a weaker constant-separation invariant. Adjoining one idempotent generates the full monoid, and the generated submonoid is contained in exactly one maximal proper submonoid, of cardinality . The submonoid generated by lazy maps alone has elements, and for both generating sets the maximum shortest-word length is six. The criterion and the cardinalities and are formally verified in Lean.
Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 9 pages