×

Bases for pseudovarieties closed under bideterministic product. (English) Zbl 1453.20076

Summary: We show that if \(\mathsf{V}\) is a semigroup pseudovariety containing the finite semilattices and contained in \(\mathsf{DS}\), then it has a basis of pseudoidentities between finite products of regular pseudowords if, and only if, the corresponding variety of languages is closed under bideterministic product. The key to this equivalence is a weak generalization of the existence and uniqueness of \(\mathsf{J}\)-reduced factorizations. This equational approach is used to address the locality of some pseudovarieties. In particular, it is shown that \(\mathsf{DH}\cap \mathsf{ECom}\) is local, for any group pseudovariety \(\mathsf{H}\).

MSC:

20M07 Varieties and pseudovarieties of semigroups
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
18B40 Groupoids, semigroupoids, semigroups, groups (viewed as categories)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Almeida, J.: Finite Semigroups and Universal Algebra. World Scientific, Singapore (1995). English translation
[2] Almeida, J., A syntactical proof of locality of DA, Int. J. Algebra Comput., 6, 165-177 (1996) · Zbl 0858.20052 · doi:10.1142/S021819679600009X
[3] Almeida, J.; Kudryavtsev, VB (ed.); Rosenberg, IG (ed.), Profinite semigroups and applications, 1-45 (2005), New York · Zbl 1109.20050
[4] Almeida, J.; Azevedo, A., On regular implicit operations, Portugal. Math., 50, 35-61 (1993) · Zbl 0802.20049
[5] Almeida, J.; Azevedo, A.; Teixeira, L., On finitely based pseudovarieties of the forms \(V*\) D and \(V*D_n\), J. Pure Appl. Algebra, 146, 1-15 (2000) · Zbl 0944.20041 · doi:10.1016/S0022-4049(98)00162-5
[6] Almeida, J.; Costa, A., Infinite-vertex free profinite semigroupoids and symbolic dynamics, J. Pure Appl. Algebra, 213, 605-631 (2009) · Zbl 1179.20050 · doi:10.1016/j.jpaa.2008.08.009
[7] Almeida, J.; Costa, A., Equidivisible pseudovarieties of semigroups, Publ. Math. Debrecen, 90, 435-453 (2017) · Zbl 1399.20058 · doi:10.5486/PMD.2017.7634
[8] Almeida, J.; Costa, A.; Costa, JC; Zeitoun, M., The linear nature of pseudowords, Publ. Mat., 63, 361-422 (2019) · Zbl 1508.20071 · doi:10.5565/PUBLMAT6321901
[9] Almeida, J.; Escada, A., The globals of some subpseudovarieties of DA, Int. J. Algebra Comput., 14, 525-549 (2004) · Zbl 1066.20500 · doi:10.1142/S0218196704001967
[10] Almeida, J.; Weil, P., Reduced factorizations in free profinite groups and join decompositions of pseudovarieties, Int. J. Algebra Comput., 4, 375-403 (1994) · Zbl 0818.20024 · doi:10.1142/S0218196794000051
[11] Almeida, J.; Weil, P.; Fountain, JB (ed.), Relatively free profinite monoids: an introduction and examples, No. 466, 73-117 (1995), Dordrecht · Zbl 0877.20038 · doi:10.1007/978-94-011-0149-3_4
[12] Almeida, J.; Weil, P., Profinite categories and semidirect products, J. Pure Appl. Algebra, 123, 1-50 (1998) · Zbl 0891.20037 · doi:10.1016/S0022-4049(96)00083-7
[13] Auinger, K., Join decompositions of pseudovarieties involving semigroups with commuting idempotents, J. Pure Appl. Algebra, 170, 115-129 (2002) · Zbl 1004.20041 · doi:10.1016/S0022-4049(01)00081-0
[14] Azevedo, A.: Operações implícitas sobre pseudovariedades de semigrupos. Aplicações. Ph.D. thesis, Universidade do Porto (1989)
[15] Branco, MJJ, On the Pin-Thérien expansion of idempotent monoids, Semigroup Forum, 49, 329-334 (1994) · Zbl 0821.20043 · doi:10.1007/BF02573494
[16] Branco, MJJ, Two algebraic approaches to variants of the concatenation product, Theor. Comput. Sci., 369, 406-426 (2006) · Zbl 1140.68024 · doi:10.1016/j.tcs.2006.09.017
[17] Branco, MJJ, Deterministic concatenation product of languages recognized by finite idempotent monoids, Semigroup Forum, 74, 379-409 (2007) · Zbl 1127.20036 · doi:10.1007/s00233-006-0669-3
[18] Costa, A., Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts, J. Pure Appl. Algebra, 209, 517-530 (2007) · Zbl 1130.20043 · doi:10.1016/j.jpaa.2006.06.016
[19] Costa, A.; Escada, A., Some operators that preserve the locality of a pseudovariety of semigroups, Int. J. Algebra Comput., 23, 583-610 (2013) · Zbl 1278.20075 · doi:10.1142/S0218196713500112
[20] Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976) · Zbl 0359.94067
[21] Jiang, Z., On the Pin-Thérien expansion of completely regular monoids, Semigroup Forum, 60, 1-3 (2000) · Zbl 0976.20048 · doi:10.1007/s002330010001
[22] Jones, PR, Monoid varieties defined by \(x^{n+1}=x\) are local, Semigroup Forum, 47, 318-326 (1993) · Zbl 0790.20087 · doi:10.1007/BF02573769
[23] Jones, PR, Profinite categories, implicit operations and pseudovarieties of categories, J. Pure Appl. Algebra, 109, 61-95 (1996) · Zbl 0852.18005 · doi:10.1016/0022-4049(95)00074-7
[24] Jones, PR; Szendrei, MB, Local varieties of completely regular monoids, J. Algebra, 150, 1-27 (1992) · Zbl 0774.20036 · doi:10.1016/S0021-8693(05)80045-6
[25] Kaďourek, J., On the locality of the pseudovariety DG, J. Inst. Math. Jussieu, 7, 93-180 (2008) · Zbl 1147.20051 · doi:10.1017/S1474748007000059
[26] Pin, J.E.: Propriétés syntactiques du produit non ambigu. In: Automata, languages and programming (Proc. Seventh Internat. Colloq., Noordwijkerhout, 1980), Lect. Notes in Comput. Sci., vol. 85, pp. 483-499. Springer, Berlin (1980) · Zbl 0448.68018
[27] Pin, J. E., Varieties, 27-44 (1986), Boston, MA · doi:10.1007/978-1-4613-2215-3_3
[28] Pin, JE; Rozenberg, G. (ed.); Salomaa, A. (ed.), Syntactic semigroups, chap. 10 (1997), New York
[29] Pin, JE; Straubing, H.; Thérien, D., Locally trivial categories and unambiguous concatenation, J. Pure Appl. Algebra, 52, 297-311 (1988) · Zbl 0645.20046 · doi:10.1016/0022-4049(88)90097-7
[30] Pin, JE; Thérien, D., The bideterministic concatenation product, Int. J. Algebra Comput., 3, 535-555 (1993) · Zbl 0816.20065 · doi:10.1142/S0218196793000305
[31] Pin, JE; Weil, P., Profinite semigroups, Mal’cev products and identities, J. Algebra, 182, 604-626 (1996) · Zbl 0857.20040 · doi:10.1006/jabr.1996.0192
[32] Reiterman, J., The Birkhoff theorem for finite algebras, Algebra Universalis, 14, 1-10 (1982) · Zbl 0484.08007 · doi:10.1007/BF02483902
[33] Rhodes, J., Steinberg, B.: The \(q\)-Theory of Finite Semigroups. Springer Monographs in Mathematics. Springer, New York (2009) · Zbl 1186.20043
[34] Straubing, H., Aperiodic homomorphisms and the concatenation product of recognizable sets, J. Pure Appl. Algebra, 15, 319-327 (1979) · Zbl 0407.20056 · doi:10.1016/0022-4049(79)90025-2
[35] Tilson, B., Categories as algebra: an essential ingredient in the theory of monoids, J. Pure Appl. Algebra, 48, 83-198 (1987) · Zbl 0627.20031 · doi:10.1016/0022-4049(87)90108-3
[36] Trotter, PG; Weil, P., The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue, Algebra Universalis, 37, 491-526 (1997) · Zbl 0906.20036 · doi:10.1007/s000120050033
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.