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).



Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>