×
Blanchet-Sadri, F.

Games, equations and dot-depth two monoids. (English) Zbl 0791.20068

Discrete Appl. Math. 39, No. 2, 99-111 (1992).
Some questions concerning the dot-depth hierarchy \({\mathcal V}_ k\) and its sub-hierarchies \({\mathcal V}_{k,m}\) are studied. The approach taken by the author is based on a class of congruences \(\sim \overline{m}\) defined on free monoids for every sequence \(\overline{m} = (m_ 1,\dots,m_ k)\) of positive integers. Such congruences arise from an extension of the standard Ehrenfeucht-Fraisse game due to W. Thomas. The author provides some systems of equations which are satisfied by \({\mathcal V}_{2,m}\), and for an alphabet \(A\) of cardinality at least two obtains, amongst other things, necessary and sufficient conditions for \(A^*/\sim (m_ 1,\dots,m_ k)\) to be of dot-depth exactly 2.
Reviewer: M.V.Lawson (Bangor)

Cited in 8 Documents

MSC:

20M07 Varieties and pseudovarieties of semigroups
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata

Keywords:

dot-depth hierarchy; class of congruences; free monoids; Ehrenfeucht- Fraisse game
Cite Review PDF
Full Text: DOI

References:

[1] Blanchet-Sadri, F., On dot-depth two, RAIRO Inform. Théor. Appl., 24, 521-530 (1990) · Zbl 0718.68046
[2] Blanchet-Sadri, F., Some logical characterizations of the dot-depth hierarchy and applications, (Tech. Rept. 88-03 (1988), Department of Mathematics and Statistics, McGill University: Department of Mathematics and Statistics, McGill University Montreal, Que), 1-44 · Zbl 0831.68066
[3] Blanchet-Sadri, F., Games, equations and the dot-depth hierarchy, Comput. Math. Appl., 18, 809-822 (1989) · Zbl 0682.03015
[4] Brzozowski, J. A.; Knast, R., The dot-depth hierarchy of star-free languages is infinite, J. Comput. System Sci., 16, 37-55 (1978) · Zbl 0368.68074
[5] Brzozowski, J. A.; Simon, I., Characterizations of locally testable events, Discrete Math., 4, 243-271 (1973) · Zbl 0255.94032
[6] Cohen, R. S.; Brzozowski, J. A., Dot-depth of star-free events, J. Comput. System Sci., 5, 1-16 (1971) · Zbl 0217.29602
[7] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. Math., 49, 129-141 (1961) · Zbl 0096.24303
[8] Eilenberg, S., Automata, Languages and Machines, Vol. B (1972), Academic Press: Academic Press New York
[9] Enderton, H. B., A Mathematical Introduction to Logic (1972), Academic Press: Academic Press New York · Zbl 0298.02002
[10] Knast, R., A semigroup characterization of dot-depth one languages, RAIRO Inform. Théor., 17, 321-330 (1983) · Zbl 0522.68063
[11] Knast, R., Some theorems on graph congruences, RAIRO Inform. Théor., 17, 331-342 (1983)
[12] McNaughton, R.; Papert, S., Counter-Free Automata (1971), MIT Press: MIT Press Cambridge, MA · Zbl 0232.94024
[13] Perrin, D.; Pin, J. E., First order logic and star-free sets, J. Comput. System Sci., 32, 393-406 (1986) · Zbl 0618.03015
[14] Pin, J. E., Variétés de Languages Formels (1984), Masson: Masson Paris · Zbl 0636.68093
[15] Pin, J. E., Hierarchies de concatenation, RAIRO Inform. Théor., 18, 23-46 (1984) · Zbl 0559.68062
[16] Rosenstein, J. G., Linear Orderings (1982), Academic Press: Academic Press New York · Zbl 0179.01303
[17] Schützenberger, M. P., On finite monoids having only trivial subgroups, Inform. and Control, 8, 190-194 (1965) · Zbl 0131.02001
[18] Simon, I., Piecewise testable events, (Proceedings of the 2nd GI Conference. Proceedings of the 2nd GI Conference, Lecture Notes in Computer Science, 33 (1975), Springer: Springer Berlin), 214-222 · Zbl 0316.68034
[19] Straubing, H., A generalization of the Schützenberger product of finite monoids, Theoret. Comput. Sci., 13, 137-150 (1981) · Zbl 0456.20048
[20] Straubing, H., Finite semigroup varieties of the form \(V^∗D\), J. Pure Appl. Algebra, 36, 53-94 (1985) · Zbl 0561.20042
[21] Straubing, H., Semigroups and languages of dot-depth two, (Proceedings of the 13th ICALP, Lecture Notes in Computer Science, 226 (1986), Springer: Springer New York), 416-423 · Zbl 0596.68056
[22] Thomas, W., Classifying regular events in symbolic logic, J. Comput. System Sci., 25, 360-376 (1982) · Zbl 0503.68055
[23] Thomas, W., An application of the Ehrenfeucht-Fraisse game in formal language theory, Bull. Soc. Math. France, 16, 11-21 (1984) · Zbl 0558.68064
[24] Tilson, B., Categories as Algebra, J. Pure Appl. Algebra, 48, 83-198 (1987) · Zbl 0627.20031
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.