This post continues the discussion on the Kleene theorem from here. The previous post gave a notion of regular expressions that had the same expressive power as nondeterministic automata. The idea was that a star corresponds to a graph where the set of vertices had one orbit, and where the edges where labelled by simpler regular expressions. In the case without atoms, such a graph is necessarily a self loop, which corresponds to the standard Kleene star. This post is about a stronger requirement: instead of saying that the graph has one orbit of vertices, we say that it has one orbit of edges.
In this post, I try to give a characterization of standard alphabets (i.e. alphabets where Turing machines determinize) which works for many choices of atoms.
Theorem. Assume that the atoms are oligomorphic, have a decidable first-order theory, and for every one can compute the number of orbits of -tuples of atoms. The following conditions are equivalent for every orbit finite set .
- Turing machines over input alphabet determinize
- There exists a function which is computable by a deterministic Turing machine, and such that two words are in the same orbit if and only if they have the same image under .
One research direction to consider is rewriting systems with orbit-finite sets of rules. There is a nice application to knot theory.
Fact. Suppose that is a one-orbit set and
is an equivariant function. Then is a bijection.