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?

# Tag Archives: standard alphabet

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

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