Frame cellular automata: Configurations, generating sets and related matroids

We introduce a frame cellular automaton as a broad generalization of an earlier study on quasigroup-defined cellular automata. It consists of a triple (F,R,EF)(F,R,EF) where, for a given finite set XX of cells, the frame FF is a family of subsets of XX (called elementary frames, denoted SiSi, i=1,…,ni=1,…,n), which is a cover of XX. A matching configuration is a map c¯:X→G which attributes to each cell a state in a finite set GG under restriction of a set of local rules R={Ri∣i=1,…n}R={Ri∣i=1,…n}, where RiRi holds in the elementary frame SiSi and is determined by an (|Si||Si|-1)-ary quasigroup over GG. The frame associated map EFEF models how a matching configuration can be grown iteratively from a certain initial cell-set. General properties of frames and related matroids are investigated. A generating set S⊂XS⊂X is a set of cells such that there is a bijection between the collection of matching configurations and GSGS. It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.