zbMATH — the first resource for mathematics

Closure of varieties of languages under products with counter. (English) Zbl 0766.20023
Let \(L_ 0,\dots,L_ k\) be languages over some alphabet \(A\), let \(a_ 1,\dots,a_ k\) be letters of \(A\), let \(r,t\in\mathbb{N}\) and let \(n\in\mathbb{N}- \{0\}\). The product with counter \(r,n,t\) of these languages is then the language denoted \((L_ 0a_ 1L_ 1\dots a_ kL_ k)_{r,n,t}\) that consists in the words \(w\) such that the number of factorizations of the form \(w=u_ 0a_ 1u_ 1\dots a_ ku_ k\) with \(u_ i\in L_ i\) is congruent to \(r\) mod \(n\) threshold \(t\). This paper is essentially devoted to the characterization and the study of the fine structure of the language varieties in the sense of Eilenberg that are closed under product with counter. Some decidability results for these kinds of varieties are also given at the end of the paper.
Reviewer: D.Krob (Paris)

20M35 Semigroups in automata theory, linguistics, etc.
20M07 Varieties and pseudovarieties of semigroups
68Q45 Formal languages and automata
Full Text: DOI
[1] Azevedo, A., Operações implicitas sobre pseudovariedades de semigrupos, aplicações, ()
[2] Barrington, D., Bounded-width polynomial-size branching programs recognize only those languages in NC1, J. comput. system sci., 38, 150-164, (1989) · Zbl 0667.68059
[3] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart, Germany · Zbl 0424.68040
[4] Elenberg, S., ()
[5] Kleene, S., Representation of events in nerve nets and finite automata, (), 3-51
[6] Pin, J.-E., Varietes de langages et variétés de semigroupes, () · Zbl 0398.68035
[7] Pin, J.-E., Concatenation hierarchies and decidability results, (), 195-228
[8] Pin, J.-E.; Pin, J.-E., Varieties of formal languages, (1986), Masson Paris, Plenum, New York · Zbl 0632.68069
[9] Pin, J.-E., Finite group topology and p-adic topoly for free monoids, (), 445-455
[10] Straubing, H., Recognizable sets and power sets of finite semigroups, Semigroup forum, 18, 331-340, (1979) · Zbl 0433.20045
[11] Straubing, H., Families of recognizable sets corresponding to certain varieties of finite monoids, J. pure appl. algebra, 15, 305-318, (1979) · Zbl 0414.20056
[12] Straubing, H., Aperiodic homomorphisms and the concatenation product of recognizable sets, J. pure appl. algebra, 15, 319-327, (1979) · Zbl 0407.20056
[13] Straubing, H., A generalization of the schützenberger product of finite monoids, Theoret. comput. sci., 13, 137-150, (1981) · Zbl 0456.20048
[14] Straubing, H., Semigroups and languages of dot-depth two, Theoret. comput. sci., 58, 361-378, (1988) · Zbl 0655.18004
[15] Straubing, H.; Thérien, D.; Thomas, W., Regular languages defined with generalized quantifiers, () · Zbl 0658.68098
[16] Thérien, D., Classification of finite monoids: the language approach, Theoret. comput. sci., 14, 195-208, (1981) · Zbl 0471.20055
[17] Thérien, D., Subword counting and nilpotent groups, (), 297-305
[18] \scB. Tilson, Chaps. XI, XII in [4].
[19] Weil, P., Products et décomposition d’automates, applications à la théorie des langages, ()
[20] Weil, P., Inverse monoids and the dot-depth hierarchy, ()
[21] Weil, P., An extension of the schützenberger product, () · Zbl 0742.20066
[22] Weil, P., Products of languages with counter, Theoret. comput. sci., 76, 251-260, (1990) · Zbl 0704.68071
[23] Weil, P., Concatenation product: A survey, (), 120-137
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.