pipette
ENEnglish

Generation by lazy and invertible cellular automata over the Klein four-group

Edgar Alcal\'{a}-Arroyo, Alonso Castillo-Ramirez, Haobo Ma, and Wenlin Zhang

Preprint

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 9 pages