Given a basis of pseudoidentities for a pseudovariety of ordered semigroups containing the 5-element aperiodic Brandt semigroup , under the natural order, it is shown that the same basis, over the most general graph over which it can be read, defines the global. This is used to show that the global of the pseudovariety of level of Straubing-Thérien’s concatenation hierarchy has infinite vertex rank.
@article{ITA_2005__39_1_1_0,
author = {Almeida, Jorge and Escada, Ana P.},
title = {The globals of pseudovarieties of ordered semigroups containing $B\_2$ and an application to a problem proposed by Pin},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {39},
year = {2005},
pages = {1-29},
doi = {10.1051/ita:2005001},
mrnumber = {2132576},
zbl = {1079.20074},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2005__39_1_1_0}
}
Almeida, Jorge; Escada, Ana P. The globals of pseudovarieties of ordered semigroups containing $B_2$ and an application to a problem proposed by Pin. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) pp. 1-29. doi : 10.1051/ita:2005001. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_1_0/
[1] , Hyperdecidable pseudovarieties and the calculation of semidirect products. Int. J. Algebra Comput. 9 (1999) 241-261. | Zbl 1028.20038
[2] , A syntactical proof of locality of DA. Int. J. Algebra Comput. 6 (1996) 165-177. | Zbl 0858.20052
[3] , Finite Semigroups and Universal Algebra. World Scientific, Singapore (1995). English translation. | MR 1331143 | Zbl 0844.20039
[4] , Finite semigroups: an introduction to a unified theory of pseudovarieties, in Semigroups, Algorithms, Automata and Languages, edited by G.M.S. Gomes, J.-E. Pin and P.V. Silva. World Scientific, Singapore (2002) 3-64. | Zbl 1033.20067
[5] , and, On finitely based pseudovarieties of the forms and . J. Pure Appl. Algebra 146 (2000) 1-15. | Zbl 0944.20041
[6] and, Globals of commutative semigroups: the finite basis problem, decidability, and gaps. Proc. Edinburgh Math. Soc. 44 (2001) 27-47. | Zbl 0993.20035
[7] and, Profinite categories and semidirect products. J. Pure Appl. Algebra 123 (1998) 1-50. | Zbl 0891.20037
[8] , Polynomial operations and rational languages, 4th STACS. Lect. Notes Comput. Sci. 247 (1991) 198-206. | Zbl 0635.68078
[9] , Opérations polynomiales et hiérarchies de concaténation. Theor. Comput. Sci. 91 (1991) 71-84. | Zbl 0751.68031
[10] , Hierarchies of aperiodic languages. RAIRO Inform. Théor. 10 (1976) 33-49.
[11] and, The dot-depth hierarchy of star-free languages is infinite. J. Comp. Syst. Sci. 16 (1978) 37-55. | Zbl 0368.68074
[12] and, Characterizations of locally testable events. Discrete Math. 4 (1973) 243-271. | Zbl 0255.94032
[13] , Automata, Languages and Machines, Vol. B. Academic Press, New York (1976). | MR 530383 | Zbl 0359.94067
[14] and, The theorem of Knast, the and type II conjecture, in Monoids and Semigroups with Applications, edited by J. Rhodes. World Scientific (1991) 453-463. | Zbl 0826.20054
[15] , Profinite categories, implicit operations and pseudovarieties of categories. J. Pure Applied Algebra 109 (1996) 61-95. | Zbl 0852.18005
[16] , A semigroup characterization of dot-depth one languages. RAIRO Inform. Théor. 17 (1983) 321-330. | Numdam | Zbl 0522.68063
[17] , Some theorems on graphs congruences. RAIRO Inform. Théor. 17 (1983) 331-342.
[18] , Inverse Semigroups: the Theory of Partial Symmetries. World Scientific, Singapore (1998). | MR 1694900 | Zbl 1079.20505
[19] and, Product of group languages, FCT Conference. Lect. Notes Comput. Sci. 199 (1985) 285-299. | Zbl 0602.68063
[20] , Algebraic decision procedures for local testability. Math. Systems Theor. 8 (1974) 60-76. | Zbl 0287.02022
[21] , A variety theorem without complementation. Izvestiya VUZ Matematika 39 (1985) 80-90. English version, Russian Mathem. (Iz. VUZ) 39 (1995) 74-83. | Zbl 0852.20059
[22] , Syntactic Semigroups, Chapter 10 in Handbook of Formal Languages, edited by G. Rosenberg and A. Salomaa, Springer (1997). | MR 1470002
[23] , Bridges for concatenation hierarchies, in 25th ICALP, Berlin. Lect. Notes Comput. Sci. 1443 (1998) 431-442. | Zbl 0909.68113
[24] and, Monoids of upper triangular matrices, Colloquia Mathematica Societatis Janos Boylai 39, Semigroups, Szeged (1981) 259-272. | Zbl 0635.20028
[25] and, A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis 35 (1996) 577-595. | Zbl 0864.03024
[26] and, Polynomial closure and unambiguous product. Theory Comput. Syst. 30 (1997) 1-39. | Zbl 0872.68119
[27] , and, Ordered categories and ordered semigroups. Comm. Algebra 30 (2002) 5651-5675. | Zbl 1017.06007
[28] , Free combinatorial strict inverse semigroups. J. London Math. Soc. 39 (1989) 102-120. | Zbl 0636.20032
[29] , The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1-10. | Zbl 0484.08007
[30] , Piecewise testable events, in Proc. 2th GI Conf., Lect. Notes Comput. Sci. 33 (1975) 214-222. | Zbl 0316.68034
[31] , The product of rational languages, in Proc. ICALP 1993, Lect. Notes Comput. Sci. 700 (1993) 430-444.
[32] , A generalization of the Schützenberger product of finite monoids. Theor. Comp. Sci. 13 (1981) 137-150. | Zbl 0456.20048
[33] , Finite semigroup varieties of the form . J. Pure Appl. Algebra 36 (1985) 53-94. | Zbl 0561.20042
[34] , Semigroups and languages of dot-depth two. Theor. Comput. Sci. 58 (1988) 361-378. | Zbl 0655.18004
[35] and, On a conjecture concerning dot-depth two languages. Theor. Comput. Sci. 104 (1992) 161-183. | Zbl 0762.68037
[36] and, Graph congruences and wreath products. J. Pure Appl. Algebra 36 (1985) 205-215. | Zbl 0559.20042
[37] , Categories as algebras: an essential ingredient in the theory of monoids. J. Pure Appl. Algebra 48 (1987) 83-198. | Zbl 0627.20031
[38] , Some results on the dot-depth hierarchy. Semigroup Forum 46 (1993) 352-370. | Zbl 0778.20025