Logical aspects in the study of tree languages. (English) Zbl 0557.68051

Thomas, Wolfgang

Trees in algebra and programming, 9th Colloq., Bordeaux/France 1984, 31-49 (1984).

[For the entire collection see Zbl 0538.00024.]
A considerable part of the theory of finite automata extends in a rather direct way to tree automata, but there are some notable exceptions. Among these is the refined theory of regular languages based on syntactic monoids; here it is not even obvious how the central concepts should be defined. In this paper the author considers the possibilities to extend the theory of star-free languages which has grown around the celebrated theorem of Schützenberger. Syntactic monoids and aperiodicity are defined for tree languages in a very plausible way, and it is then easily seen that a regular tree language is aperiodic iff its syntactic monoid is group-free. However, it turns out that these languages are not the same as the star-free tree languages. At this point the author resorts to model-theoretic methods. By restricting set variables either to chains or to antichains in tree domains, two restricted forms of monadic second- order definability are obtained. It is shown that the chain definable and the antichain definable tree languages form two mutually incomparable subclasses of the regular tree languages, and that both of these classes properly include the class of first-order definable tree languages. Using the machinery of m-theories from the model theory of linear orderings the author achieves the following two characterizations: (1) A tree language is star-free iff it is antichain definable; (2) A chain definable tree language is aperiodic iff it is first-order definable. These results and the approach advocated by the author could have a vitalizing effect on the theory of regular tree languages which has suffered from a shortage of interesting subclasses. The author also presents some open problems and suggests directions for further research. A more complete account of this work is promised.

Reviewer: M.Steinby

MSC:

68Q45	Formal languages and automata
20M35	Semigroups in automata theory, linguistics, etc.
03C99	Model theory

Keywords:

tree automata; syntactic monoids; star-free languages; aperiodicity; tree languages; chains; antichains; monadic second-order definability; regular tree languages; m-theories

Citations:

Zbl 0538.00024