×

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

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\}\).

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
PDF BibTeX XML Cite
Full Text: DOI EuDML

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
[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
[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
[6] Brzozowski, J. A. and I. Simon,Characterizations of locally testable events, Discr. Math.4 (1973), 243–271. · Zbl 0255.94032
[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
[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
[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
[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
[19] Thomas, W.,An application of the Ehrenfeucht-Fraïssé game in formal language theory, Bull. Soc. Math. France16 (1984), 11–21.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.