Abstract:

As far as computations are finite, finite-state devices can be viewed
as ''very simple''. This is no more true for finite-state automata
running over infinite words or trees, the latter can actually go
beyond the hierarchy, which E.Borel designed as a universe of feasible
mathematics.

Topological aspect of infinite computations has been recognized already
by Buchi. Topological hardness is often an evidence for infeasibility
results for various models of automata. J.R.Buchi and L.H.Landweber, and
later K.Wagner described completely topological properties of automata on
infinite words. These results were  recently extended to deterministic
automata on infinite trees. In particular, F.Murlak described the Wadge
hierarchy of deterministic tree languages. Te non-deterministic case remains
largely open.

Another complexity measure for tree automata stems from the concept of
index, related to the Mu-calculus and infinite games. The index hierarchy and
topological hierarchies are closely related, but they do not grow with the
same pace: each one is sometimes finer than the other. Again, we know how to
effectively decide the index hierarchy only in the deterministic case.

All decidability results are based on detecting some ''forbidden patterns''
in deterministic automata, which are responsible for the hardness (in the
topological, or combinatorial sense).

This is a joint work with Andre Arnold, Filip Murlak, and Igor Walukiewicz