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.
All posts by Mikołaj
A Kleene Theorem with Atoms
Standard alphabets beyond equality atoms
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 
.
Rewriting
One research direction to consider is rewriting systems with orbit-finite sets of rules. There is a nice application to knot theory.
Equivariant endomorphisms
Fact. Suppose that 
is a one-orbit set and
![\[f : X \to X\]](https://atoms.mimuw.edu.pl/wp-content/ql-cache/quicklatex.com-0777a5128e1af7764f6d6e04c5792039_l3.svg "Rendered by QuickLaTeX.com")
is an equivariant function. Then is a bijection.