The globals of pseudovarieties of ordered semigroups containing B 2 and an application to a problem proposed by Pin

Jorge Almeida; Ana P. Escada

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

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

Abstract

top
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.

How to cite

top

Almeida, 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. [1] J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products. Int. J. Algebra Comput. 9 (1999) 241–261. Zbl1028.20038
  2. [2] J. Almeida, A syntactical proof of locality of DA. Int. J. Algebra Comput. 6 (1996) 165–177. Zbl0858.20052
  3. [3] J. Almeida, Finite Semigroups and Universal Algebra. World Scientific, Singapore (1995). English translation. Zbl0844.20039MR1331143
  4. [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. [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. [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. [7] J. Almeida and P. Weil, Profinite categories and semidirect products. J. Pure Appl. Algebra 123 (1998) 1–50. Zbl0891.20037
  8. [8] M. Arfi, Polynomial operations and rational languages, 4th STACS. Lect. Notes Comput. Sci. 247 (1991) 198–206. Zbl0635.68078
  9. [9] M. Arfi, Opérations polynomiales et hiérarchies de concaténation. Theor. Comput. Sci. 91 (1991) 71–84. Zbl0751.68031
  10. [10] J.A. Brzozowski, Hierarchies of aperiodic languages. RAIRO Inform. Théor. 10 (1976) 33–49. 
  11. [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. [12] J.A. Brzozowski and I. Simon, Characterizations of locally testable events. Discrete Math. 4 (1973) 243–271. Zbl0255.94032
  13. [13] S. Eilenberg, Automata, Languages and Machines, Vol. B. Academic Press, New York (1976). Zbl0359.94067MR530383
  14. [14] K. Henckell and J. Rhodes, The theorem of Knast, the P G = B G and type II conjecture, in Monoids and Semigroups with Applications, edited by J. Rhodes. World Scientific (1991) 453–463. Zbl0826.20054
  15. [15] P. Jones, Profinite categories, implicit operations and pseudovarieties of categories. J. Pure Applied Algebra 109 (1996) 61–95. Zbl0852.18005
  16. [16] R. Knast, A semigroup characterization of dot-depth one languages. RAIRO Inform. Théor. 17 (1983) 321–330. Zbl0522.68063
  17. [17] R. Knast, Some theorems on graphs congruences. RAIRO Inform. Théor. 17 (1983) 331–342. 
  18. [18] M.V. Lawson, Inverse Semigroups: the Theory of Partial Symmetries. World Scientific, Singapore (1998). Zbl1079.20505MR1694900
  19. [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. [20] R. McNaughton, Algebraic decision procedures for local testability. Math. Systems Theor. 8 (1974) 60–76. Zbl0287.02022
  21. [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. [22] J.-E. Pin, Syntactic Semigroups, Chapter 10 in Handbook of Formal Languages, edited by G. Rosenberg and A. Salomaa, Springer (1997). MR1470002
  23. [23] J.-E. Pin, Bridges for concatenation hierarchies, in 25th ICALP, Berlin. Lect. Notes Comput. Sci. 1443 (1998) 431–442. Zbl0909.68113
  24. [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. [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. [26] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Comput. Syst. 30 (1997) 1–39. Zbl0872.68119
  27. [27] J.-E. Pin, A. Pinguet and P. Weil, Ordered categories and ordered semigroups. Comm. Algebra 30 (2002) 5651–5675. Zbl1017.06007
  28. [28] N. Reilly, Free combinatorial strict inverse semigroups. J. London Math. Soc. 39 (1989) 102–120. Zbl0636.20032
  29. [29] J. Reiterman, The Birkhoff theorem for finite algebras. Algebra Universalis 14 (1982) 1–10. Zbl0484.08007
  30. [30] I. Simon, Piecewise testable events, in Proc. 2th GI Conf., Lect. Notes Comput. Sci. 33 (1975) 214–222. Zbl0316.68034
  31. [31] I. Simon, The product of rational languages, in Proc. ICALP 1993, Lect. Notes Comput. Sci. 700 (1993) 430–444. 
  32. [32] H. Straubing, A generalization of the Schützenberger product of finite monoids. Theor. Comp. Sci. 13 (1981) 137–150. Zbl0456.20048
  33. [33] H. Straubing, Finite semigroup varieties of the form V * D . J. Pure Appl. Algebra 36 (1985) 53–94. Zbl0561.20042
  34. [34] H. Straubing, Semigroups and languages of dot-depth two. Theor. Comput. Sci. 58 (1988) 361–378. Zbl0655.18004
  35. [35] H. Straubing and P. Weil, On a conjecture concerning dot-depth two languages. Theor. Comput. Sci. 104 (1992) 161–183. Zbl0762.68037
  36. [36] D. Thérien and A. Weiss, Graph congruences and wreath products. J. Pure Appl. Algebra 36 (1985) 205–215. Zbl0559.20042
  37. [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. [38] P. Weil, Some results on the dot-depth hierarchy. Semigroup Forum 46 (1993) 352–370. Zbl0778.20025

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.