On dot-depth two. (English) Zbl 0718.68046

Blanchet-Sadri, F.

RAIRO, Inform. Théor. Appl. 24, No. 6, 521-529 (1990).

If A is a finite alphabet then the Straubing hierarchy is: \(A^*V_ o=\{0,A^*\}\) and \(A^*V_{k+1}=\{L\subseteq A^ A{}^*| L\) is a boolean combination of languages of the form \(L_ oa_ 1L_ 1a_ 2...a_ nL_ n(n\geq o)\) with \(L_ o,...\), \(L_ n\in A^*V_ k\), \(a_ 1,...,a_ n\in A\}.\)
A language \(L\subseteq A^*\) is star-free if and only if \(L\in A^*V_ k\) for some \(k\geq 0\). The smallest k such that \(L\in A^*V_ k\) is the dot-depth of L.
The paper investigates the open problem whether it is decidable if a given language has the dot-depth k (which is equivalent to the problem of effectively characterizing the monoids \(M=A^*/\sim\) where \(\sim \supseteq \sim \bar m\), \(\sim \bar m\) defined in the paper, \(\bar m=(m_ 1,...,m_ k)\), \(m_ i\in {\mathbb{N}}\), \(1\leq i\leq k)\). The main result of this paper is that for positive integers \(m_ 1\), \(m_ 2\), \(m_ 3\), the monoid \(A^*/\sim (m_ 1,m_ 2,m_ 3)\) is of dot-depth exactly 2 if and only if \(m_ 2=1\).

Reviewer: G.Grigoras (Iaşi)

MSC:

68Q45	Formal languages and automata
03D05	Automata and formal grammars in connection with logical questions
03D55	Hierarchies of computability and definability

Keywords:

regular language; Straubing hierarchy; star-free; dot-depth

References:

[1]	1. J. A. BRZOZOWSKI and R. KNAST, The Dot-Depth Hierarchy of Star-Free Languages if Infinite, J. Comp. Sys. Sci., 1978, 16, pp. 37-55. Zbl0368.68074 MR471451 · Zbl 0368.68074 · doi:10.1016/0022-0000(78)90049-1
[2]	2. F. BLANCHET-SADRI, Some Logical Characterizations of the Dot-Depth Hierarchy and Applications, Technical Report No. 88-03 of the Department of Mathematics and Statistics of McGill University, July 1988, pp. 1-44. MR2685431
[3]	3. F. BLANCHET-SADRI, Games, Equations and the Dot-Depth Hierarchy, (preprint 1988 ), Computers and Mathematics with applications (à paraître). Zbl0682.03015 MR1008808 · Zbl 0682.03015 · doi:10.1016/0898-1221(89)90179-X
[4]	4. R. S. COHEN and J. A. BRZOZOWSKI, Dot-Depth of Star-Free Events, J. Comp. Sys. Sci., 1971, 5, pp. 1-16. Zbl0217.29602 MR309676 · Zbl 0217.29602 · doi:10.1016/S0022-0000(71)80003-X
[5]	5. A. EHRENFEUCHT, An Application of Games to the Completeness Problem for Formalized Theories, Fund. Math., 1961, 49, pp. 129-141. Zbl0096.24303 MR126370 · Zbl 0096.24303
[6]	6. S. EILENBERG, Automata, Languages and Machines, B, Academic Press, New York, 1976. Zbl0359.94067 MR530383 · Zbl 0359.94067
[7]	7. H. B. ENDERTON, A Mathematical Introduction to Logic, Academic Press, New York, 1972. Zbl0298.02002 MR337470 · Zbl 0298.02002
[8]	8. R. FRAISSÉ, Cours de logique mathématique, tome 2, Gauthier-Vîllars, Paris, 1972. Zbl0247.02003 MR446871 · Zbl 0247.02003
[9]	9. G. LALLEMENT, Semigroups and Combinatorial Applications, Wiley, New York, 1979. Zbl0421.20025 MR530552 · Zbl 0421.20025
[10]	10. R. MCNAUGHTON and S. PAPERT, Counter-Free Automata, M.I.T. Press, Cambridge, Mass., 1971. Zbl0232.94024 MR371538 · Zbl 0232.94024
[11]	11. D. PERRIN and J. E. PIN, First-Order Logic and Star-Free Sets, J. Comp. Sys. Sci., 1986, 32, pp. 393-406. Zbl0618.03015 MR858236 · Zbl 0618.03015 · doi:10.1016/0022-0000(86)90037-1
[12]	12. J. E. PIN, Variétés de langages formels, Masson, Paris, 1984. Zbl0636.68093 MR752695 · Zbl 0636.68093
[13]	13. J. E. PIN, Hiérarchies de contaténation, R.A.I.R.O. Informatique Théorique, 1984, 18, pp. 23-46. Zbl0559.68062 MR750449 · Zbl 0559.68062
[14]	14. J. G. ROSENSTEIN, Linear Orderings, Academic Press, New York, 1982. Zbl0488.04002 MR662564 · Zbl 0488.04002
[15]	15. M. P. SCHÜTZENBERGER, On Finite Monoids having only Trivial Subgroups, Information and Control, 1965, 8, pp. 190-194. Zbl0131.02001 MR176883 · Zbl 0131.02001 · doi:10.1016/S0019-9958(65)90108-7
[16]	16. I. SIMON, Piecewise Testable Events, Proc. 2nd GI Conference, Lectures Notes in Comput Sci., Springer Verlag, Berlin, 1975, 33, pp. 214-222. Zbl0316.68034 MR427498 · Zbl 0316.68034
[17]	17. H. STRAUBING, A Generalization of the Schützenberger Product of Finite Monoids, Theoretical Comput Sci., 1981, 13, pp. 137-150. Zbl0456.20048 MR594057 · Zbl 0456.20048 · doi:10.1016/0304-3975(81)90036-0
[18]	18. H. STRAUBING, Finite Semigroup Varieties of the Form V*D, J. of Pure and Applied Algebra, 1985, 36, pp. 53-94. Zbl0561.20042 MR782639 · Zbl 0561.20042 · doi:10.1016/0022-4049(85)90062-3
[19]	19. H. STRAUBING, Semigroups and Languages of Dot-Depth Two, Proc. 13th ICALP, Lecture Notes in Comput. Sci., Springer Verlag, New York, 1986, 226, pp. 416- 423. Zbl0596.68056 MR864704 · Zbl 0596.68056
[20]	20. W. THOMAS, Classifying Regular Events in Symbolic Logic, J. Comp. Sys. Sci., 1982, 25, pp. 360-376. Zbl0503.68055 MR684265 · Zbl 0503.68055 · doi:10.1016/0022-0000(82)90016-2
[21]	21. W. THOMAS, An Application of the Ehrenfeucht-Fraissé Game in Formal Language Theory, Bull. Soc. Math. de France, 2e série, Mémoire, 1984, No. 16, pp. 11-21. Zbl0558.68064 MR792490 · Zbl 0558.68064
[22]	22. B. TILSON, Categories as Algebra, J. of Pure and Applied Algebra, 1987, 48, pp. 83-198. Zbl0627.20031 MR915990 · Zbl 0627.20031 · doi:10.1016/0022-4049(87)90108-3