PhD Dissertation

Author Saeed Salehi
Title Varieties of Tree Languages
Language English
Supervisor Professor Magnus Steinby
Reviewers (1) Professor Zoltán Ésik
(2) Professor Wolfgang Thomas
Opponent Professor Thomas Wilke
Defence Date 12 August 2005

Abstract and Table of Contents of the thesis are down the page below.
Here is the PhD Dissertation (128 pages).

If you are interested in having a hardcopy of the dissertation, please e-mail me at Saeed@Math.Net.
I will have a copy (in book format) sent to your postal address.

This is the set of slides of the talk I presented in my disputation; and this is an outline of the thesis (PDF file; 10 pages).

Abstract

Trees are among the most fundamental and ubiquitous structures in mathematics. Tree languages and automata on trees have been studied extensively since the 1960s from both a purely mathematical and application point of view. When trees are defined as terms, universal algebra becomes directly applicable to tree automata and, on the other hand, the theory of tree automata suggests new notions and problems to universal algebra.

Different syntactic invariants have been proposed as bases for classifications of regular tree languages: syntactic algebras (Steinby 1979, 1992; Almeida 1990), syntactic monoids and syntactic semigroups (Thomas 1983; Nivat and Podelski 1989), tree algebras (Wilke 1996) and syntactic theories (Ésik 1999). However, so far variety theorems comparable with Eilenberg�s classical theorems for regular string languages were known for syntactic algebras and syntactic theories only. In this thesis we consider several aspects of varieties of tree languages and settle some open questions concerning the various formalisms.

In Chapter 2 we extend the variety theorem for general recognizable subsets of free algebras (Steinby 1979) to the many-sorted case. In Chapter 3 we formulate Pin�s (1996) theory of positive varieties for tree languages and prove a variety theorem that establishes a correspondence between positive varieties of tree languages and varieties of finite ordered algebras.

It has been known already for quite a long time that not all varieties of tree languages can be defined by syntactic monoids or syntactic semigroups, and the question about the exact defining power of these syntactic invariants has been raised by several authors. In Chapter 4 we answer this question by characterizing the varieties of tree languages that correspond to some variety of finite monoids or semigroups. In Chapter 5 we characterize families of tree languages definable by ordered monoids and study some special instances of the above mentioned variety theorems.

Chapter 6 is devoted to Wilke�s tree algebras. We introduce a convergent term rewriting system that yields an efficient method to decide the word problem of tree algebras. As a special case of the many-sorted theory developed in Chapter 2 we obtain a variety theorem for families of tree languages defined by tree algebras. Moreover, we prove that, for any sufficiently rich alphabet, all congruence-preserving functions of the tree term algebra are obtained as compositions of the basic tree-constructing operations.

Table of Contents

1 Introduction and preliminaries 1
2 Many-sorted variety theorem 9
   2.1 Many-sorted algebras 10
   2.2 Syntactic congruences and algebras 16
   2.3 The variety theorem 21
3 Positive varieties of tree languages 29
   3.1 Ordered algebras 30
   3.2 Positive variety theorem 35
   3.3 Generalized positive variety theorem 40
4 Definability by monoids 47
   4.1 Algebras definable by translation monoids 49
   4.2 Tree languages definable by monoids 52
   4.3 Definability by semigroups 59
5 Definability by ordered monoids 65
   5.1 Ordered algebras vs. ordered monoids 65
   5.2 Tree languages definable by ordered monoids 69
   5.3 Examples of varieties 76
6 Tree algebras 87
   6.1 Binary trees and tree algebras 88
   6.2 Varieties of binary tree languages 94
   6.3 Some algebraic properties of tree algebras 100
Epilogue 107
Index of Notation 109
References 113




home Back to Home-Page
Hosted by www.Geocities.ws

1