Equations and dot-depth one. (English) Zbl 0814.20048

Blanchet-Sadri, F.

Semigroup Forum 47, No. 3, 305-317 (1993).

Let \(V_{k,m}\) denote the finite monoid varieties corresponding to the Straubing hierarchy of star-free languages. The author studies whether these varieties are finitely based. For every pair of integers \(r \geq 0\), \(m \geq 1\) a finite sequence of equations \(C_ m^ r\) is constructed such that \(C_ m^ 0 = \{x^ m = x^{m+1}\}\) and \(C_ m^ r \sqsubseteq C_ m^ s\) if \(r \leq s\).
Theorem 1: Let \(M\) be a monoid generated by a set of \(r + 1\) elements, \(r \geq 0\). Then \(M\) belongs to \(V_{1,m}\) iff \(M\) satisfies the equations in \(C_ m^ r\). The equations \(\bigcup\{C_ m^ r : r \geq 0\}\) define the variety \(V_{1,m}\). Theorem 2: The family of equations \(\bigcup\{C_ m^ r : r \geq 0\}\) is equivalent to \(C_ m^ s\), where \(s= 1\) if \(m \in \{1,2\}\) and \(s = 2\) if \(m = 3\). Thus the variety \(V_{1,m}\) is finitely based if \(m = 1,2,3\). The author also constructs for every \(m\) a finite sequence of equations \(D_ m\) such that for every finite monoid \(M\) generated by \(2\) elements, \(M \in V_{2,1}\) iff \(M\) ultimately satisfies the equations in \(\bigcup\{D_ m : m \geq 1\}\).

Reviewer: A.A.Iskander (Lafayette)

MSC:

20M35	Semigroups in automata theory, linguistics, etc.
20M07	Varieties and pseudovarieties of semigroups
68Q45	Formal languages and automata
20M05	Free semigroups, generators and relations, word problems

Keywords:

finitely based varieties; finite monoid varieties; Straubing hierarchy; star-free languages; sequence of equations

References:

[1]	Blanchet-Sadri, F., ”Some Logical Characterizations of the Dot-Depth Hierarchy and Applications,” Ph.D. Thesis, McGill University, 1989. · Zbl 0682.03015
[2]	Blanchet-Sadri, F.,Games, equations and the dot-depth hierarchy, Computers Math. Applic.18 (1989), 809–822. · Zbl 0682.03015 · doi:10.1016/0898-1221(89)90179-X
[3]	Blanchet-Sadri, F.,On dot-depth two, RAIRO Inform. Théor. Applic.24 (1990), 521–529. · Zbl 0718.68046
[4]	Blanchet-Sadri, F.,Games, equations and dot-depth two monoids, Discr. Appl. Math.39 (1992), 99–111. · Zbl 0791.20068 · doi:10.1016/0166-218X(92)90161-3
[5]	Brzozowski, J. A. and R. Knast,The dot-dept hierarchy of star-free languages is infinite, J. Comp. Sys. Sci.16 (1978), 37–55. · Zbl 0368.68074 · doi:10.1016/0022-0000(78)90049-1
[6]	Brzozowski, J. A. and I. Simon,Characterizations of locally testable events, Discr. Math.4 (1973), 243–271. · Zbl 0255.94032 · doi:10.1016/S0012-365X(73)80005-6
[7]	Cohen, R. S. and J. A. Brzozowski,Dot-depth of star-free events, J. Comp. Sys. Sci.5 (1971), 1–15. · Zbl 0217.29602 · doi:10.1016/S0022-0000(71)80003-X
[8]	Eilenberg, S., ”Automata, Languages and Machines B,” Academic Press, New York, 1976. · Zbl 0359.94067
[9]	Knast, R.,A semigroup characterization of dot-depth one languages, RAIRO Inform. Théor.17 (1983), 321–330. · Zbl 0522.68063
[10]	Knast, R.,Some theorems on graph congruences, RAIRO Inform. Théor.17 (1983), 331–342.
[11]	Lallement, G., ”Semigroups and Combinatorial Applications,” Wiley, N.Y., 1979. · Zbl 0421.20025
[12]	McNaughton, R. and S. Papert, ”Counter-free Automata,” MIT Press, Cambridge, Mass., 1971. · Zbl 0232.94024
[13]	Pin, J.-E., ”Variétés de Langages Formels,” Masson, Paris, 1984.
[14]	Schützenberger, M. P.,On finite monoids having only trivial subgroups, Inform. Control8 (1965), 190–194. · Zbl 0131.02001 · doi:10.1016/S0019-9958(65)90108-7
[15]	Simon, I.,Piecewise testable events, In: Proc. Second GI Conf., Lect. Notes in Comp. Sci.33 (1975), 214–222.
[16]	Straubing, H.,Finite semigroup varieties of the form V*D, Pure Appl. Algebra36 (1985), 53–94. · Zbl 0561.20042 · doi:10.1016/0022-4049(85)90062-3
[17]	Straubing, H.,Semigroups and languages of dot-depth two, In: Proc. Thirteenth ICALP, Lect. Notes in Comp. Sci.226 (1986), 416–423. · Zbl 0596.68056
[18]	Thomas, W.,Classifying regular events in symbolic logic, J. Comp. Sys. Sci.25 (1982), 360–376. · Zbl 0503.68055 · doi:10.1016/0022-0000(82)90016-2
[19]	Thomas, W.,An application of the Ehrenfeucht-Fraïssé game in formal language theory, Bull. Soc. Math. France16 (1984), 11–21.