General Varieties of Tree Languages

M. Steinby

IBP-Litp 1995/30: 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

Résumé : Nous considérons des variétés générales de langages d'arbres non restreintes à un alphabet à arités fixes, des variétés générales d'algèbres finies qui contiennentdes algèbres finies de tous les tvariété est prouvé qui établit une triple correspondance entre les treillis formés par ces trois types de variétés sous la forme de trois coypes finis, et la notion correspondante de variété de congruences. Un théorème de uples d'isomorphismes inverses l'un de l'autre. A cette fin, les notions de sous-algèbres, congruences, morphismes, et produits directs sont généralisées pour pouvoir être aussi utilisées quand les algèbres traitées sont de différentstypes finis, et nous généralisons aussi les parties correspondantes de l'algèbre universelle de base. Les congruences syntaxiques et les algèbres syntaxiques de langagesd'arbres sont redéfinies de manière similaire. Nous montrons que nombre de familles usuelles de langages d'arbres régulierssont des variétés générales de langages d'arbres en notre sens. De plus, nous prouvons que toute famille de langages d'arbres réguliers définissable par monoides syntaxiques, est une variété générale.

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