Rapport de Recherche Litp /
Litp research reports
50 pages - Juin/June 1995 - Document en anglais.
PostScript : Ko /Kb
Titre / Title: General Varieties of Tree Languages
Abstract : We consider general varieties of tree languages which are not restricted to a fixed ranked alphabet, generalized varieties of finite algebras which contain finite algebras of all finite types, and a corresponding notion of varieties of congruences. A Variety Theorem is proved which establishes a triple correspondence between the lattices formed by these three types of varieties in the form three pairs of mutually inverse isomorphisms. To obtain this, subalgebras, congruences, morphisms, and direct products are generalized so that the notions can be used also when the algebras involved are of different (finite) types, and we also generalize the appropriate parts of basic universal algebra. Syntactic congruences and syntactic algebras of tree languages are redefined in a corresponding manner. Many known families of special regular tree languages are shown to be general varieties of tree languages in our sense. Moreover, we prove that any family of regular tree languages which can be defined by syntactic monoids, is such a variety.
Publications internes Litp 1995 / Litp research reports 1995