We study a derivation quasi-order between between alphabets. Whenever is derived from and is non-standard then is non-standard too. We identify also a class of minimal non-standard alphabets wrt. the quasi-order.
Consider equality atoms . Call orbit-finite sets alphabets. An alphabet is standard if all Turing machines over this alphabet determinize.
For a letter of an alphabet, let denote the least support of , and let the automphism group of be the set of those permutations of that extend to an atom automorphism. In other words, is the stabilizer of restricted to .
Definition. An alphabet is derived from an alphabet if for every there is a word such that is a projection of .
Fact. Alphabets derived from a standard alphabet are standard.
Proof (sketch). If , derived from , is non-standard, then is also non-standard, as a finite word may be used to emulate every letter .
By the above facts, there are minimal non-standard alphabets wrt. the derivation. As the derivation is a quasi-order, the minimal non-standard alphabets are not necessarily determined uniquely.
One possible choice of these minimal alphabets is one-ortbit triangular alphabets, which is actually a property of the automorphism groups of letters of that alphabet. A finite permutation group is triangular if has three orbits in and there is a permutation such that the projection of on every two (out of three) orbits extends to a permutation in , while itself is not in .
Fact. An alphabet is non-standard if and only if some triangular alphabet is derived from .
Proof (idea). Using the following characterization of standard alphabets: is standard iff the arity of equals 2, for all .
Theorem. For two alphabets , it is decidable whether is derived from .
Proof (idea). Using a very close relationship between the derivation of an alphabet from , and the so called pp-definability of the (CSP) template (induced by ) in the template (induded by ).