No Access

ORDERED AND -TRIVIAL SEMIGROUPS AS DIVISORS OF SEMIGROUPS OF LANGUAGES

ALEXEI VERNITSKI

Department of Mathematical Sciences, University of Essex, Colchester, Essex, C04 3SQ, UK

https://doi.org/10.1142/S021819670800486XCited by:3 (Source: Crossref)

Abstract

A semigroup of languages is a set of languages considered with (and closed under) the operation of catenation. In other words, semigroups of languages are subsemigroups of power-semigroups of free semigroups. We prove that a (finite) semigroup is positively ordered if and only if it is a homomorphic image, under an order-preserving homomorphism, of a (finite) semigroup of languages. Hence it follows that a finite semigroup is -trivial if and only if it is a homomorphic image of a finite semigroup of languages.

Keywords:

AMSC: 20M35, 68Q70, 06F05, 20M07

References

J. Almeida , Finite Semigroups and Universal Algebra ( World Scientific , Singapore , 1994 ) . Google Scholar
S. V. Avgustinovich and A. E. Frid, Int. J. Algebra Comput. 15, 149 (2005), DOI: 10.1142/S0218196705002116. Link, Web of Science, Google Scholar
C. Choffrut, J. Karhumäki and N. Ollinge, Theor. Comput. Sci. 273, 69 (2002), DOI: 10.1016/S0304-3975(00)00434-5. Crossref, Web of Science, Google Scholar
K. Henckell and J.-E. Pin, Ordered monoids and J-trivial monoids, Algorithmic Problems in Groups and Groups and Semigroups, Based on Talks Given at the International Conference, Trends in Mathematics (Birkhäuser, Boston, MA, 2000) pp. 121–137. Google Scholar
P. M. Higgins, Theor. Comput. Sci. 178, 257 (1997), DOI: 10.1016/S0304-3975(96)00230-7. Crossref, Web of Science, Google Scholar
S. Margolis and J.-E. Pin, Semigroup Forum 29, 99 (1984), DOI: 10.1007/BF02573319. Crossref, Web of Science, Google Scholar
J. E. Pin , Varieties of Formal Languages ( Plenum Publishing Corporation , New York , 1986 ) . Crossref, Google Scholar
J.-E. Pin, Finite semigroups and recognizable languages: An introduction, Semigroups, Formal Languages and Groups, Proceedings of NATO Advanced Study Institute, NATO Advanced Science Institute Series, Series C, Mathematical and Physical Science 466, ed. F. John (Kluwer Academic Publishers, Dordrecht, 1995) pp. 1–32. Google Scholar
A. Salomaa and S. Yu, On the decomposition of finite languages, Proc. Development on Language Theory 1999, eds. G. Rozenberg and W. Thomas (World Scientific, Singapore, 2000) pp. 22–31. Google Scholar
H. J. Shyr and Y. S. Tsai, Discrete Math. 181, 213 (1998), DOI: 10.1016/S0012-365X(97)00037-X. Crossref, Web of Science, Google Scholar
H. J. Shyr and S. S. Yu, Int. J. Comput. Math. 68, 243 (1998), DOI: 10.1080/00207169808804692. Crossref, Web of Science, Google Scholar
I. Simon, Piecewise testable events, Proc. 2nd GI Conference, Lecture Notes in Computer Science 33 (Springer, Berlin, 1975) pp. 214–222. Google Scholar
H. Straubing, Semigroup Forum 19, 107 (1980), DOI: 10.1007/BF02572507. Crossref, Web of Science, Google Scholar
H. Straubing and D. Thérien, J. Algebra 119, 393 (1988), DOI: 10.1016/0021-8693(88)90067-1. Crossref, Web of Science, Google Scholar
M. V. Volkov, Int. J. Algebra Comput. 14, 817 (2004), DOI: 10.1142/S0218196704002018. Link, Web of Science, Google Scholar