SYNTACTIC MONOIDS OF TREE LANGUAGES

ABSTRACT: Syntactic monoids and syntactic semigroups have proved extremely useful in the study of regular languages. Moreover, Eilenberg's Variety Theorem, that establishes a bijection between varieties of finite monoids (or semigroups) and varieties of regular languages, has been the generally accepted framework for the classification theory of regular languages ever since it was presented in 1976.
Various ways of extending the theory of syntactic monoids and varieties of languages to trees have been proposed. In this lecture we shall first review briefly the main approaches. Although more properties of a tree language can be expressed by its syntactic algebra than by its syntactic monoid, and syntactic algebras also yield a Variety Theorem, syntactic monoids of tree languages are of considerable interest, too. After a brief survey of the main facts about them, we shall consider also syntactic path monoids; this new notion seems to be suitable for the study of deterministic root-to-frontier tree languages.