## Tree Canonization and Transitive Closure

- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- September 13, 1995 at 1:00 PM

### Abstract:

In this talk we provide tight upper and lower bounds on the
logical expressibility of tree isomorphism and related problems. We
show that (bounded degree) tree isomorphism is not expressible in
first-order transitive-closure logic with counting quantifiers (the
logic (FO + TC + COUNT)). The proof uses an Ehrenfeucht-Fraisse game
that characterizes the logic (FO + TC + COUNT). As a corresponding
upper bound we show that tree canonization is expressible via a
first-order sentence with counting quantifiers iterated O(log n) times
(the logic (FO + COUNT)[log n]), and we show that for bounded degree
trees FO[log n] (without counting) suffices.
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.)