Derived alphabets

We study a derivation quasi-order between between alphabets. Whenever $B$ is derived from $A$ and $B$ is non-standard then $A$ is non-standard too. We identify also a class of minimal non-standard alphabets wrt. the quasi-order.

Consider equality atoms $\atoms$ . Call orbit-finite sets alphabets. An alphabet is standard if all Turing machines over this alphabet determinize.

For a letter $a$ of an alphabet, let $\sup{a}$ denote the least support of $a$ , and let the automphism group $\aut{a}$ of $a$ be the set of those permutations of $\sup{a}$ that extend to an atom automorphism. In other words, $\aut{a}$ is the stabilizer of $a$ restricted to $\sup{a}$ .

Definition. An alphabet $B$ is derived from an alphabet $A$ if for every $b \in B$ there is a word $w \in A^*$ such that $\aut{a}$ is a projection of $\aut{w}$ .

Fact. Alphabets derived from a standard alphabet are standard.

Proof (sketch). If $B$ , derived from $A$ , is non-standard, then $A$ is also non-standard, as a finite word $w \in A^*$ may be used to emulate every letter $b \in B$ .

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 $G \leq \sym{X}$ is triangular if $G$ has three orbits in $X$ and there is a permutation $\tau \in \sym{X}$ such that the projection of $\tau$ on every two (out of three) orbits extends to a permutation in $G$ , while $\tau$ itself is not in $G$ .

Fact. An alphabet $A$ is non-standard if and only if some triangular alphabet is derived from $A$ .

Proof (idea). Using the following characterization of standard alphabets: $A$ is standard iff the arity of $\aut{w}$ equals 2, for all $w \in A^*$ .

Theorem. For two alphabets $A, B$ , it is decidable whether $B$ is derived from $A$ .

Proof (idea). Using a very close relationship between the derivation of an alphabet $B$ from $A$ , and the so called pp-definability of the (CSP) template $T_B$ (induced by $B$ ) in the template $T_A$ (induded by $A$ ).

Atompress

Leave a Reply Cancel reply

Computation with atoms