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?

TCL is first-order logic extended by the transitive closure operator – which allows to define the transitive closure R^+ of a relation R of arity 2k defined earlier, where R is treated as a binary relation over k-tuples. DTCL is similar, except for that the operator only works if the relation R is a partial function (i.e., is deterministic); otherwise the operator returns the empty relation.

Note that over linearly ordered structures, the logic TCL captures NL, while DTCL captures L. In particular, it is not known whether the two logics are equivalent over finite structures equipped with a linear order. However, it is known that in general, they are not equivalent:

Theorem (Grädel and McColm). Over the class of all finite structures, DTCL is strictly less expressive than TCL, i.e., there is a property of finite structures which is expressible in TCL but not in DTCL.

This property is graph connectedness, which is clearly expressible in TCL. To show  that it is not expressible in DTCL, one uses the following argument.

For a graph G=(V,E), let 2G denote the graph with vertex set V\times\set{0,1}, and edges are ((v,i),(w,j)) where (v,w)\in E and i,j\in\set{0,1}. One then shows that over graphs of the form 2G, the logic DTCL collapses to FO logic, and FO logic cannot determine connectedness. For a tuple u=((u_1,i_1),\ldots,(u_k,i_k)) of elements vertices of 2G, let \bar u denote the set \set{u_1,\ldots,u_k}\times \set{0,1}. Because any bijection of 2G leaving the first component of each vertex fixed is an automorphism of 2G, it is easy to see that no deterministic path starting from u can leave the set \bar u, so has length bounded by some number n, where depends only on k, and not on the graph G. Therefore, the DTCL operator can be replaced by a FO formula (by an n-fold expansion of the transitive closure).

The question is: does this argument give some separation result for Turing Machines with Atoms? For example, that L and NL are different, over some alphabets? And is there a notion of a standard alphabet suited for L?


I think that the right notion of a C-standard alphabet is as follows. Let C be a complexity class with atoms. An alphabet A is C-standard if over the alphabet A, the class C doesn’t increase in power after extending it by the choice oracle – an oracle which, for a given letter provides a tuple of atoms supporting it, of bounded length (the machine equipped with the oracle should accept or not regardless of the choices made by the oracle, similarly as in order-invariant Turing machines).

The notion of a standard alphabet (over equality atoms) which we considered earlier is the same thing as the notion of a Det-standard alphabet, or, as it turns out, as the notion of a P-standard alphabet, according to the above definition. The notion of a Log-standard alphabet also makes sense, and it is not clear – as Mikołaj mentions in the comment – whether this notion is equivalent  standardness. Also, it is not clear what the definition of a LogSpace machine with atoms should be: in one definition, the auxiliary tapes can store log-many symbols from an orbit-finite alphabet, and in another definition – from a finite alphabet. I think that the construction from the  Gradel-McColm theorem might provide an example of an alphabet which is standard but not Log-standard, for one of the two definitions of the class LogSpace.


One thought on “Log-standard alphabets”

  1. A stupid comment: L and NL are different on some alphabets by padding. That is, for every nonstandard alpahbet, the following language is in NL but not in deterministically decidable (and therefore not in L): the set of words wv^n such that w and v are in the same orbit, and n=2^{|w|}.

    But this does not invalidate the last question in your post: which alphabets are Log standard? The padding argument shows that every Log-standard alphabet is P-standard. Does the converse hold?

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>