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

# Log-standard alphabets

A result of Grädel and McColm shows that over finite structures, the logic DTCL is strictly less expressive than the logic TCL. My question is: can this result be translated into some separation result concerning Turing machines with atoms?

# Existence of least supports for Fraisse atoms

In Automata theory in nominal sets (Thm. 9.3), we provided a necessary and sufficient criterion for the existence of least finite supports for arbitrary atoms. It was not clear whether the criterion could be significantly simplified for Fraisse atoms. I show that it cannot be made as simple as we originally conjectured.

# Rewriting

One research direction to consider is rewriting systems with orbit-finite sets of rules. There is a nice application to knot theory.

# Characterization of Standard Alphabets

In this paper (accepted to LICS 14) we characterize those alphabets for which Turing machines with atoms determinize.
Continue reading

# Standard alphabets vs. homogenizability

We study the relationship between standard alphabets over the equality atoms, and those which can be made homogeneous using finitely many relations and functions. We leave open the problem whether these notions coincide.

# A conjecture concerning Brzozowski algorithm (PRIZE!)

Fix attention on equality atoms.

Given an orbit-finite, deterministic automaton on the alphabet of atoms, a Brzozowski phase amounts to:

• reversing the direction of all transition arrows and swapping initial and accepting states,
• determinising the result, and
•  cutting to the reachable part.

# Derived alphabets

We study a derivation quasi-order between between alphabets. Whenever is derived from and is non-standard then is non-standard too. We identify also a class of minimal non-standard alphabets wrt. the quasi-order.

# A pumping lemma for automata with atoms

This is a straightforward generalization of the classical Pumping Lemma for regular languages. It was proved independently by the Warsaw team and by Filippo Bonchi, Daniela Petrisan and Alexandra Silva.

# Least supports and the representation theorem

This post discusses equivalence of:

1. existence of the least supports

2. representation theorem