All posts by Mikołaj

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.

Continue reading

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 n one can compute the number of orbits of n-tuples of atoms. The following conditions are equivalent for every orbit finite set B.

  1. Turing machines over input alphabet B determinize
  2. There exists a function  f :B^* \to \set{0,1}^* 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 f.

Continue reading