On a complete set of generators for dot-depth two. (English) Zbl 0793.68087

Blanchet-Sadri, F.

Discrete Appl. Math. 50, No. 1, 1-25 (1994).

Summary: A complete set of generators for Straubing’s dot-depth-two monoids has been characterized as a set of quotients of the form \(A^*/\sim_{(n,m)}\), where \(n\) and \(m\) denote positive integers, \(A^*\) denotes the free monoid generated by a finite alphabet \(A\), and \(\sim_{(n,m)}\) denote congruences related to a version of the Ehrenfeucht-Fraïssé game. The paper studies combinatorial properties of the \(\sim_{(n,m)}\)’s and in particular the inclusion relations between them. Several decidability and inclusion consequences are discussed.

MSC:

68Q45	Formal languages and automata
03B25	Decidability of theories and sets of sentences
20M35	Semigroups in automata theory, linguistics, etc.

Keywords:

dot-depth hierarchy; circuit complexity; dot-depth-two monoids; Ehrenfeucht-Fraïssé game; decidability

References:

[1]	Blanchet-Sadri, F., Some logical characterizations of the dot-depth hierarchy and applications, (Ph.D. Thesis (1989), McGill University: McGill University Montreal, Que) · Zbl 0831.68066
[2]	Blanchet-Sadri, F., Games, equations and the dot-depth hierarchy, Comput. Math. Appl., 18, 809-822 (1989) · Zbl 0682.03015
[3]	Blanchet-Sadri, F., Combinatorial properties of some congruences related to dot-depth \(k\), (Tech. Rept. No. 89-27 (1989), Department of Mathematics and Statistics of McGill University: Department of Mathematics and Statistics of McGill University Montreal, Que), 1-29 · Zbl 0793.68087
[4]	Blanchet-Sadri, F., On dot-depth two, RAIRO Inform. Théor. Appl., 24, 521-529 (1990) · Zbl 0718.68046
[5]	F. Blanchet-Sadri, Games, equations and dot-depth two monoids, Discrete Appl. Math., to appear.; F. Blanchet-Sadri, Games, equations and dot-depth two monoids, Discrete Appl. Math., to appear. · Zbl 0791.20068
[6]	Brzozowski, J. A.; Knast, R., The dot-depth hierarchy of star-free languages is infinite, Comput. System Sci., 16, 37-55 (1978) · Zbl 0368.68074
[7]	Cohen, R. S.; Brzozowski, J. A., Dot-depth of star-free events, Comput. System Sci., 5, 1-15 (1971) · Zbl 0217.29602
[8]	Ebbinghaus, H.-D.; Flum, J.; Thomas, W., Mathematical Logic (1984), Springer: Springer New York · Zbl 0556.03001
[9]	Eilenberg, S., Automata, Languages and Machines, Vol. B (1976), Academic Press: Academic Press New York · Zbl 0359.94067
[10]	McNaughton, R.; Papert, S., Counter-Free Automata (1971), MIT Press: MIT Press Cambridge, MA · Zbl 0232.94024
[11]	Perrin, D.; Pin, J.-E., First-order logic and star-free sets, Comput. System Sci., 32, 393-406 (1986) · Zbl 0618.03015
[12]	Pin, J.-E., Variétés de Langages Formels (1984), Masson: Masson Paris · Zbl 0636.68093
[13]	Pin, J.-E., Hiérarchies de concaténation, RAIRO Inform. Théor., 18, 23-46 (1984) · Zbl 0559.68062
[14]	Schützenberger, M. P., On finite monoids having only trivial subgroups, Inform. and Control, 8, 190-194 (1965) · Zbl 0131.02001
[15]	Simon, I., Piecewise testable events, (Proceedings of the Second GI Conference, Lecture Notes in Computer Science, 33 (1975), Springer: Springer Berlin), 214-222 · Zbl 0316.68034
[16]	Straubing, H., Finite semigroup varieties of the form \(V*D\), Pure Appl. Algebra, 36, 53-94 (1985) · Zbl 0561.20042
[17]	Straubing, H., Semigroups and languages of dot-depth two, (Proceedings of the Thirteenth ICALP, Lecture Notes in Computer Science, 226 (1986), Springer: Springer New York), 416-423 · Zbl 0596.68056
[18]	Thomas, W., Classifying regular events in symbolic logic, Comput. System Sci., 25, 360-376 (1982) · Zbl 0503.68055
[19]	Thomas, W., An application of the Ehrenfeucht—Fraïssé game in formal language theory, Bull. Soc. Math. France, 16, 11-21 (1984) · Zbl 0558.68064
[20]	Thomas, W., A concatenation game and the dot-depth hierarchy, (Böger, E., Computation Theory and Logic, Lecture Notes in Computer Science, 270 (1987), Springer: Springer New York), 415-426 · Zbl 0643.68073