Magnus Steinby
Deterministic top-down (dT) tree recognizers (also known as deterministic root-to-frontier tree recognizers) define a proper subfamily DRec of the family Rec of all regular tree languages. Although this family excludes even some very simple tree languages, it has many interesting properties. In particular, every context-free language is the yield of a dT tree language. On the other hand, DRec is not a variety of tree languages, and hence it cannot be characterized in the usual way by syntactic algebras or syntactic monoids.
Any dT tree language T is determined by its path languages, where each path language consists of the words formed by the labels of the nodes, augmented with indices showing the directions taken, along a path in some tree belonging to T from the root to a leaf labeled with a given leaf symbol.
In this lecture we first present a Nerode-like theorem for dT tree languages, where the Nerode congruence of a tree language is derived from the path languages of the tree language. Then, extending the same idea, we introduce syntactic path congruences and syntactic path monoids of tree languages. The syntactic path monoid of a tree language T is finite iff T is in Drec, and it can be computed as the transition monoid of a certain automaton. The lecture is mainly based on joint work with F. Gécseg.
Reference:
F. Gécseg and M. Steinby: Minimal recognizers and syntactic monoids of DR tree languages. In: Words, Semigroups and Transductions (eds. M. Ito, G. Paun and S. Yu), World Scientific, Singapore 2001, 155-167.