Products of languages with counter. (English) Zbl 0704.68071

Summary: It is well known that varieties of rational languages are in one-to-one correspondence with varieties of finite monoids. This correspondence often extends to operations on languages and on monoids. We investigate the special case of the product of languages with counter, and describe the associated operations on monoids and varieties.


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI


[1] Blanchard, P., Morphismes et comptages sur les langages rationnels, J. Inform. Process. Cybernet., 23, 3-11 (1987) · Zbl 0635.68087
[2] Brzozowski, J.; Fich, F., Languages of \(R\)-trivial monoids, J. Comput. System Sci., 20, 32-49 (1980) · Zbl 0446.68066
[3] Brzozowski, J.; Simon, I., Characterization of locally testable events, Discrete Math., 4, 243-271 (1973) · Zbl 0255.94032
[4] Eilenberg, S., Automata, Languages and Machines, Vol. B (1976), Academic Press: Academic Press New York · Zbl 0359.94067
[5] Kleene, S., Representation of events in nerve nets and finite automata, (Shannon; McCarthy, Automata Studies (1954), Princeton University Press: Princeton University Press Princeton), 3-51
[6] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[7] McNaughton, R., Algebraic decision procedures for local testability, Math. Systems Theory, 8, 60-76 (1974) · Zbl 0287.02022
[8] Pin, J.-E., Variétés de Langages Formels, Varieties of Formal Languages. Varieties of Formal Languages, Varieties of Formal Languages (1986), Masson: Masson Paris: North Oxford Academic: Masson: Masson Paris: North Oxford Academic London: Plenum Press: Masson: Masson Paris: North Oxford Academic: Masson: Masson Paris: North Oxford Academic London: Plenum Press New York · Zbl 0636.68093
[9] Pin, J.-E., Finite group topology and p-adic topology for free monoids, (Lecture Notes in Computer Science, 194 (1985), Springer: Springer Berlin), 445-455, 12th ICALP · Zbl 0576.20044
[11] Pin, J.-E.; Sakarovitch, J., Une application de la représentation matricielle des transductions, Theoret. Comput. Sci., 35, 271-293 (1985) · Zbl 0563.68064
[12] Pin, J.-E.; Straubing, H.; Thérien, D., Locally trivial categories and unambiguous concatenation, J. Pure Appl. Algebra, 52, 297-311 (1988) · Zbl 0645.20046
[13] Schützenberger, M.-P., On finite monoids having only trivial subgroups, Inform. and Control, 8, 190-194 (1965) · Zbl 0131.02001
[14] Simon, I., Piecewise testable events, (Proc. 2nd G.I. Conf.. Proc. 2nd G.I. Conf., Lecture Notes in Computer Science, 33 (1975), Springer: Springer Berlin), 214-222 · Zbl 0316.68034
[15] Straubing, H., Varieties of recognizable sets whose syntactic monoids contain solvable groups, (Ph.D. thesis (1978), University of California-Berkeley)
[16] Straubing, H., Recognizable sets and power sets of finite semigroups, Semigroup Forum, 18, 331-340 (1979) · Zbl 0433.20045
[17] Straubing, H., Families of recognizable sets corresponding to certain varieties of finite monoids, J. Pure Appl. Algebra, 15, 305-318 (1979) · Zbl 0414.20056
[18] Straubing, H., A generalization of the Schützenberger product of finite monoids, Theoret. Comput. Sci., 13, 137-150 (1981) · Zbl 0456.20048
[19] Straubing, H.; Thérien, D.; Thomas, W., Regular languages defined with generalized quantifiers, (Lepistö, T.; Salomaa, A., Lecture Notes in Computer Science, 317 (1988), Springer: Springer Berlin), 15th ICALP · Zbl 0658.68098
[20] Thérien, D., Languages of nilpotent and solvable groups, (Proc. 6th ICALP. Proc. 6th ICALP, Lecture Notes in Computer Science, 71 (1979), Springer: Springer Berlin), 616-632 · Zbl 0416.20058
[21] Thérien, D., Classification of finite monoids: the language approach, Theoret. Comput. Sci., 14, 195-208 (1981) · Zbl 0471.20055
[22] Thérien, D., Subword counting and nilpotent groups, (Cummings, L., Combinatiries on Words, Progress and Perspectives (1983), Academic Press), 297-305 · Zbl 0572.20052
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.