Kousha Etessami

DIMACS - SYLA Postdoc

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