# A stronger Kleene theorem

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.

# A Kleene Theorem with Atoms

There are many existing regular expressions for infinite alphabets (here, here). Below is another one.

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

1. Turing machines over input alphabet determinize
2. 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 is an equivariant function. Then is a bijection.