## 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
Full Text:

### References:

  Blanchet-Sadri, F., ”Some Logical Characterizations of the Dot-Depth Hierarchy and Applications,” Ph.D. Thesis, McGill University, 1989. · Zbl 0682.03015  Blanchet-Sadri, F.,Games, equations and the dot-depth hierarchy, Computers Math. Applic.18 (1989), 809–822. · Zbl 0682.03015  Blanchet-Sadri, F.,On dot-depth two, RAIRO Inform. Théor. Applic.24 (1990), 521–529. · Zbl 0718.68046  Blanchet-Sadri, F.,Games, equations and dot-depth two monoids, Discr. Appl. Math.39 (1992), 99–111. · Zbl 0791.20068  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  Brzozowski, J. A. and I. Simon,Characterizations of locally testable events, Discr. Math.4 (1973), 243–271. · Zbl 0255.94032  Cohen, R. S. and J. A. Brzozowski,Dot-depth of star-free events, J. Comp. Sys. Sci.5 (1971), 1–15. · Zbl 0217.29602  Eilenberg, S., ”Automata, Languages and Machines B,” Academic Press, New York, 1976. · Zbl 0359.94067  Knast, R.,A semigroup characterization of dot-depth one languages, RAIRO Inform. Théor.17 (1983), 321–330. · Zbl 0522.68063  Knast, R.,Some theorems on graph congruences, RAIRO Inform. Théor.17 (1983), 331–342.  Lallement, G., ”Semigroups and Combinatorial Applications,” Wiley, N.Y., 1979. · Zbl 0421.20025  McNaughton, R. and S. Papert, ”Counter-free Automata,” MIT Press, Cambridge, Mass., 1971. · Zbl 0232.94024  Pin, J.-E., ”Variétés de Langages Formels,” Masson, Paris, 1984.  Schützenberger, M. P.,On finite monoids having only trivial subgroups, Inform. Control8 (1965), 190–194. · Zbl 0131.02001  Simon, I.,Piecewise testable events, In: Proc. Second GI Conf., Lect. Notes in Comp. Sci.33 (1975), 214–222.  Straubing, H.,Finite semigroup varieties of the form V*D, Pure Appl. Algebra36 (1985), 53–94. · Zbl 0561.20042  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  Thomas, W.,Classifying regular events in symbolic logic, J. Comp. Sys. Sci.25 (1982), 360–376. · Zbl 0503.68055  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.