These results were motivated by our study of weakly ordered logics. In descriptive complexity the important computational complexity classes have been characterized as exactly the properties expressible in corresponding logical languages over -ordered- structures. For example, over totally-ordered structures, the logic (FO + TC) is non-deterministic logarithmic space (the class NL) and FO[log n] is the class AC^1.
Our work on weak orderings asks "how much" ordering is necessary and sufficient for a logic to capture its corresponding complexity class. We will show how the above results and our related work answer several questions in that setting. In particular, our results separate the logics for NL and AC^1 in the presence of a weak form of ordering called One-way Local ordering which is closely related to Cook and Rackoff's JAG model for space bounded computation. On the other hand, we show that the related Two-way Local ordering allows (FO + TC + COUNT) to capture all of NL. This points the way to some interesting and challenging open questions.
(This is joint work with Neil Immerman.)