# 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 (2005)

- Volume: 39, Issue: 1, page 1-29
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topAlmeida, Jorge, and 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 39.1 (2005): 1-29. <http://eudml.org/doc/245459>.

@article{Almeida2005,

abstract = {Given a basis of pseudoidentities for a pseudovariety of ordered semigroups containing the 5-element aperiodic Brandt semigroup $B_2$, 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 $3/2$ of Straubing-Thérien’s concatenation hierarchy has infinite vertex rank.},

author = {Almeida, Jorge, Escada, Ana P.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {semigroup; pseudovariety; semigroupoid; category; pseudoidentity; dot-depth; concatenation hierarchies; pseudovarieties of semigroups; semigroupoids; ordered semigroups; bases of pseudoidentities; semidirect products},

language = {eng},

number = {1},

pages = {1-29},

publisher = {EDP-Sciences},

title = {The globals of pseudovarieties of ordered semigroups containing $B_2$ and an application to a problem proposed by Pin},

url = {http://eudml.org/doc/245459},

volume = {39},

year = {2005},

}

TY - JOUR

AU - Almeida, Jorge

AU - Escada, Ana P.

TI - The globals of pseudovarieties of ordered semigroups containing $B_2$ and an application to a problem proposed by Pin

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2005

PB - EDP-Sciences

VL - 39

IS - 1

SP - 1

EP - 29

AB - Given a basis of pseudoidentities for a pseudovariety of ordered semigroups containing the 5-element aperiodic Brandt semigroup $B_2$, 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 $3/2$ of Straubing-Thérien’s concatenation hierarchy has infinite vertex rank.

LA - eng

KW - semigroup; pseudovariety; semigroupoid; category; pseudoidentity; dot-depth; concatenation hierarchies; pseudovarieties of semigroups; semigroupoids; ordered semigroups; bases of pseudoidentities; semidirect products

UR - http://eudml.org/doc/245459

ER -

## References

top- [1] J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Int. J. Algebra Comput. 9 (1999) 241–261. Zbl1028.20038
- [2] J. Almeida, A syntactical proof of locality of DA. Int. J. Algebra Comput. 6 (1996) 165–177. Zbl0858.20052
- [3] J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1995). English translation. Zbl0844.20039MR1331143
- [4] J. Almeida, 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. Zbl1033.20067
- [5] J. Almeida, A. Azevedo and L. Teixeira, On finitely based pseudovarieties of the forms $V*D$ and $V*{D}_{n}$. J. Pure Appl. Algebra 146 (2000) 1–15. Zbl0944.20041
- [6] J. Almeida and A. Azevedo, Globals of commutative semigroups: the finite basis problem, decidability, and gaps. Proc. Edinburgh Math. Soc. 44 (2001) 27–47. Zbl0993.20035
- [7] J. Almeida and P. Weil, Profinite categories and semidirect products. J. Pure Appl. Algebra 123 (1998) 1–50. Zbl0891.20037
- [8] M. Arfi, Polynomial operations and rational languages, 4th STACS. Lect. Notes Comput. Sci. 247 (1991) 198–206. Zbl0635.68078
- [9] M. Arfi, Opérations polynomiales et hiérarchies de concaténation. Theor. Comput. Sci. 91 (1991) 71–84. Zbl0751.68031
- [10] J.A. Brzozowski, Hierarchies of aperiodic languages. RAIRO Inform. Théor. 10 (1976) 33–49.
- [11] J.A. Brzozowski and R. Knast, The dot-depth hierarchy of star-free languages is infinite. J. Comp. Syst. Sci. 16 (1978) 37–55. Zbl0368.68074
- [12] J.A. Brzozowski and I. Simon, Characterizations of locally testable events. Discrete Math. 4 (1973) 243–271. Zbl0255.94032
- [13] S. Eilenberg, Automata, Languages and Machines, Vol. B. Academic Press, New York (1976). Zbl0359.94067MR530383
- [14] K. Henckell and J. Rhodes, The theorem of Knast, the $PG=BG$ and type II conjecture, in Monoids and Semigroups with Applications, edited by J. Rhodes. World Scientific (1991) 453–463. Zbl0826.20054
- [15] P. Jones, Profinite categories, implicit operations and pseudovarieties of categories. J. Pure Applied Algebra 109 (1996) 61–95. Zbl0852.18005
- [16] R. Knast, A semigroup characterization of dot-depth one languages. RAIRO Inform. Théor. 17 (1983) 321–330. Zbl0522.68063
- [17] R. Knast, Some theorems on graphs congruences. RAIRO Inform. Théor. 17 (1983) 331–342.
- [18] M.V. Lawson, Inverse Semigroups: the Theory of Partial Symmetries. World Scientific, Singapore (1998). Zbl1079.20505MR1694900
- [19] S.W. Margolis and J.-E. Pin, Product of group languages, FCT Conference. Lect. Notes Comput. Sci. 199 (1985) 285–299. Zbl0602.68063
- [20] R. McNaughton, Algebraic decision procedures for local testability. Math. Systems Theor. 8 (1974) 60–76. Zbl0287.02022
- [21] J.-E. Pin, A variety theorem without complementation. Izvestiya VUZ Matematika 39 (1985) 80–90. English version, Russian Mathem. (Iz. VUZ) 39 (1995) 74–83. Zbl0852.20059
- [22] J.-E. Pin, Syntactic Semigroups, Chapter 10 in Handbook of Formal Languages, edited by G. Rosenberg and A. Salomaa, Springer (1997). MR1470002
- [23] J.-E. Pin, Bridges for concatenation hierarchies, in 25th ICALP, Berlin. Lect. Notes Comput. Sci. 1443 (1998) 431–442. Zbl0909.68113
- [24] J.-E. Pin and H. Straubing, Monoids of upper triangular matrices, Colloquia Mathematica Societatis Janos Boylai 39, Semigroups, Szeged (1981) 259–272. Zbl0635.20028
- [25] J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis 35 (1996) 577–595. Zbl0864.03024
- [26] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Syst. 30 (1997) 1–39. Zbl0872.68119
- [27] J.-E. Pin, A. Pinguet and P. Weil, Ordered categories and ordered semigroups. Comm. Algebra 30 (2002) 5651–5675. Zbl1017.06007
- [28] N. Reilly, Free combinatorial strict inverse semigroups. J. London Math. Soc. 39 (1989) 102–120. Zbl0636.20032
- [29] J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1–10. Zbl0484.08007
- [30] I. Simon, Piecewise testable events, in Proc. 2th GI Conf., Lect. Notes Comput. Sci. 33 (1975) 214–222. Zbl0316.68034
- [31] I. Simon, The product of rational languages, in Proc. ICALP 1993, Lect. Notes Comput. Sci. 700 (1993) 430–444.
- [32] H. Straubing, A generalization of the Schützenberger product of finite monoids. Theor. Comp. Sci. 13 (1981) 137–150. Zbl0456.20048
- [33] H. Straubing, Finite semigroup varieties of the form $V*D$. J. Pure Appl. Algebra 36 (1985) 53–94. Zbl0561.20042
- [34] H. Straubing, Semigroups and languages of dot-depth two. Theor. Comput. Sci. 58 (1988) 361–378. Zbl0655.18004
- [35] H. Straubing and P. Weil, On a conjecture concerning dot-depth two languages. Theor. Comput. Sci. 104 (1992) 161–183. Zbl0762.68037
- [36] D. Thérien and A. Weiss, Graph congruences and wreath products. J. Pure Appl. Algebra 36 (1985) 205–215. Zbl0559.20042
- [37] B. Tilson, Categories as algebras: an essential ingredient in the theory of monoids. J. Pure Appl. Algebra 48 (1987) 83–198. Zbl0627.20031
- [38] P. Weil, Some results on the dot-depth hierarchy. Semigroup Forum 46 (1993) 352–370. Zbl0778.20025

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.