2023/05/22 by Xuan Kien Phung · 1 citation
Computer Science · #Cellular Automata and Applications #semigroups and automata theory #Quantum-Dot Cellular Automata
paper · pdf · doi:10.4153/s0008414x23000329
Abstract For linear nonuniform cellular automata (NUCA) which are local perturbations of linear CA over a group universe G and a finite-dimensional vector space alphabet V over an arbitrary field k , we investigate their Dedekind finiteness property, also known as the direct finiteness property, i.e., left or right invertibility implies invertibility. We say that the group G is L1 -surjunctive, resp. finitely L1 -surjunctive, if all such linear NUCA are automatically surjective whenever they are stably injective, resp. when in addition k is finite. In parallel, we introduce the ring D1(k[G]) which is the Cartesian product k[G] × (k[G])[G] as an additive group but the multiplication is twisted in the second component. The ring D1(k[G]) contains naturally the group ring k[G] and we obtain a dynamical characterization of its stable finiteness for every field k in terms of the finite L1 -surjunctivity of the group G , which holds, for example, when G is residually finite or initially subamenable. Our results extend known results in the case of CA.