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 , E F ) where, for a given finite set X of cells, the frame F is a family of subsets of X (called elementary frames, denoted S i , i = 1 , … , n ), which is a cover of X . A matching configuration is a map c ¯ : X → G which attributes to each cell a state in a finite set G under restriction of a set of local rules R = { R i ∣ i = 1 , … n } , where R i holds in the elementary frame S i and is determined by an ( | S i | -1)-ary quasigroup over G . The frame associated map E F 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 ⊂ X is a set of cells such that there is a bijection between the collection of matching configurations and G S . It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.