Concatenation hierarchies decidability results and problems.

*(English)*Zbl 0561.68055
Combinatorics on words. Progress and perspectives, Proc. Int. Meet., Waterloo/Can. 1982, 195-228 (1983).

[For the entire collection see Zbl 0552.00014.]

This is a lucid survey of the theory of concatenation hierarchies of star-free languages with a special emphasis on recent developments in the area. After having clearly delineated the subject in the introduction, the author reviews its basic conceptual apparatus: semigroups, finite automata, syntactic congruences, varieties etc. In the second section the best-known examples of Eilenberg’s variety theorem are presented starting with Schützenberger’s classic characterization of the star-free languages. Then the general notion of a concatenation hierarchy is introduced, and the two cases studied in the literature, Brzozowski’s hierarchy and Straubing’s hierarchy, are considered. The last section is devoted to a very general method for defining concatenation hierarchies recently introduced by the author. The idea is to let the alternations of Boolean operations and concatenations to be controlled by trees. No proofs are given, but the main concepts are illustrated by examples. The few misprints and mistakes that have slipped into the text do not much detract from the good readability of the paper. Although the list of references obviously is not meant to constitute a full bibliography, it is very useful to anyone who wishes to learn about the work done in this field since Eilenberg’s great synthesis [S. Eilenberg, Automata, languages, and machines, Vol. B (1976; Zbl 0359.94067)].

This is a lucid survey of the theory of concatenation hierarchies of star-free languages with a special emphasis on recent developments in the area. After having clearly delineated the subject in the introduction, the author reviews its basic conceptual apparatus: semigroups, finite automata, syntactic congruences, varieties etc. In the second section the best-known examples of Eilenberg’s variety theorem are presented starting with Schützenberger’s classic characterization of the star-free languages. Then the general notion of a concatenation hierarchy is introduced, and the two cases studied in the literature, Brzozowski’s hierarchy and Straubing’s hierarchy, are considered. The last section is devoted to a very general method for defining concatenation hierarchies recently introduced by the author. The idea is to let the alternations of Boolean operations and concatenations to be controlled by trees. No proofs are given, but the main concepts are illustrated by examples. The few misprints and mistakes that have slipped into the text do not much detract from the good readability of the paper. Although the list of references obviously is not meant to constitute a full bibliography, it is very useful to anyone who wishes to learn about the work done in this field since Eilenberg’s great synthesis [S. Eilenberg, Automata, languages, and machines, Vol. B (1976; Zbl 0359.94067)].

##### MSC:

68Q45 | Formal languages and automata |

20M35 | Semigroups in automata theory, linguistics, etc. |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |