×

Semigroups and languages of dot-depth two. (English) Zbl 0655.18004

The author discusses the problem of membership of a finite monoid M in the i-th member \({\mathcal V}_ i\) of a sequence of pseudo-varieties of monoids corresponding to the varieties of regular languages forming the so called Brzozowski hierarchy of locally testable languages. He gives two partial results: a necessary condition for M to belong to \({\mathcal V}_ 2\); for a 2-generated M it is also a sufficient condition.
Reviewer: V.Koubek

MSC:

18B40 Groupoids, semigroupoids, semigroups, groups (viewed as categories)
20M07 Varieties and pseudovarieties of semigroups
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barrington, D.; Thérien, D., Finite monoids and the fine structure of \(NC^1\), Proc. 19th ACM STOC, 101-109 (1987), New York
[2] Brzozowski, J. A.; Cohen, R., Dot-depth of star-free events, J. Comput. System Sci., 5, 1-16 (1971) · Zbl 0217.29602
[3] Brzozowski, J. A.; Knast, R., The dot-depth hierarchy of star-free events is infinite, J. Comput. System Sci., 16, 37-55 (1978) · Zbl 0368.68074
[4] Brzozowski, J. A.; Simon, I., Characterizations of locally testable events, Discrete Math., 4, 243-271 (1973) · Zbl 0255.94032
[5] Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math., 6, 66-92 (1960) · Zbl 0103.24705
[6] Eilenberg, S., Automata, Languages and Machines, Vol. B (1976), Academic Press: Academic Press New York
[7] Fich, F.; Brzozowski, J. A., A characterization of a dot-depth two analogue of generalized definite languages, (Proc. 6th ICALP. Proc. 6th ICALP, Lecture Notes in Computer Science, 71 (1979), Springer: Springer Berlin), 230-244, Graz, Austria · Zbl 0412.68074
[8] Fust, M.; Saxe, J.; Sipser, M., Parity, circuits and the polynomial-time hierarchy, Math. Systems Theory, 18, 13-27 (1984) · Zbl 0534.94008
[9] Knast, R., A semigroup characterization of dot-depth one languages, RAIRO Inform. Théor. (1984)
[10] Ladner, R., Application of model-theoretic games to discrete linear orders and finite automata, Inform. and Control, 33, 281-303 (1977) · Zbl 0387.68037
[11] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[12] McNaughton, R., Algebraic decision procedures for local testability, Math. Systems Theory, 8, 60-76 (1974) · Zbl 0287.02022
[13] McNaughton, R.; Papert, S., Counter-Free Automata (1971), MIT Press: MIT Press Cambridge, MA · Zbl 0232.94024
[14] Perrin, D.; Pin, J. E., First-order logic and star-free events, J. Comput. System Sci., 32, 393-406 (1986) · Zbl 0618.03015
[15] Pin, J. E., Variétés de semigroupes et variétés de langages, (Thèse d’Etat (1981), Université de Paris VI) · Zbl 0402.68053
[16] Pin, J. E.; Straubing, H., Monoids of upper triangular matrices, Colloquia Math. Soc. J. Bolyai, 39, 259-272 (1985) · Zbl 0635.20028
[17] J.E. Pin, H. Straubing, and D. Thérien, Locally trivial categories and unambiguous concatenation, J. Pure Appl. Algebra; J.E. Pin, H. Straubing, and D. Thérien, Locally trivial categories and unambiguous concatenation, J. Pure Appl. Algebra · Zbl 0645.20046
[18] Rhodes, J.; Tilson, B., The kernel of monoid morphisms: a reversal-invariant decomposition theory (1987), Center for Pure and Applied Mathematics, University of California: Center for Pure and Applied Mathematics, University of California Berkeley, CA, Preprint
[19] Schützenberger, M. P., On finite monoids having only trivial subgroups, Inform. Control, 8, 190-194 (1965) · Zbl 0131.02001
[20] Simon, I., Piecewise testable events, (Proc. 2nd GI Conf.. Proc. 2nd GI Conf., Lecture Notes in Computer Science, 33 (1975), Springer: Springer Berlin) · Zbl 0316.68034
[21] Sipser, M., Borel sets and circuit complexity, Proc. 24th IEEE FOCS, 61-69 (1983)
[22] Straubing, H., A generalization of the Schützenberger product of finite monoids, Theoret. Comput. Sci., 13, 137-150 (1981) · Zbl 0456.20048
[23] Straubing, H., Finite semigroup varieties of the form \(V\)\(D\), J. Pure Appl. Algebra, 36, 53-94 (1985) · Zbl 0561.20042
[24] Straubing, H., Semigroups and languages of dot-depth two, (Proc. 13th ICALP. Proc. 13th ICALP, Lecture Notes in Computer Science, 226 (1986), Springer: Springer Berlin), 416-423, Rennes, France
[25] Straubing, H.; Thérien, D., Partially ordered finite monoids and a theorem of I. Simon, (Tech. Rept. SOCS-85.10 (1985), McGill University) · Zbl 0658.20035
[26] Thérien, D., Classification of finite monoids: the language approach, Theoret. Comput. Sci., 14, 195-208 (1981) · Zbl 0471.20055
[27] Thérien, D., Catégories et langages de dot-depth un, (Tech. Rept. SOCS-85-22 (1985), McGill University), Preprint · Zbl 0659.68094
[28] Thérien, D.; Weiss, A., Graph congruences and wreath products, J. Pure Appl. Algebra, 36, 205-215 (1985) · Zbl 0559.20042
[29] Thomas, W., Classifying regular events in symbolic logic, J. Comput. System Sci., 25, 360-376 (1982) · Zbl 0503.68055
[30] Thomas, W., An application of the Ehrenfeucht-Fraïssé game in formal language theory, Bull. Soc. Math. France, 16, 11-21 (1984) · Zbl 0558.68064
[31] B. Tilson, [6, Chapters 11 and 12].; B. Tilson, [6, Chapters 11 and 12].
[32] 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.