Special Issue: International Conference on Semigroups and Groups in Honor of the 65th Birthday of Prof. John RhodesNo Access

REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT

M. V. VOLKOV

M. V. VOLKOV

Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russia

Search for more papers by this author

https://doi.org/10.1142/S0218196704002018Cited by:23 (Source: Crossref)

Abstract

Straubing deduced from Simon's theorem that monoids of reflexive relations as well as monoids of order preserving extensive transformations generate the pseudovariety of -trivial monoids. We refine these results by showing that each pseudovariety in Simon's hierarchy of -trivial monoids is generated by a single relation/transformation monoid. From this and from some results by Blanchet–Sadri we obtain a complete solution of the finite basis problem for Straubing's monoids.

Dedicated to John Rhodes on the occasion of his 65th birthday

Keywords:

AMSC: 20M07, 20M20, 68Q70

References

J. Almeida, J. Pure Appl. Algebra 69, 205 (1990). Crossref, Web of Science, Google Scholar
F. Blanchet-Sadri, Some logical characterizations of the dot-depth hierarchy, Ph.D. thesis, McGill University (1989) . Google Scholar
F. Blanchet-Sadri, Comput. Math. Appl. 18, 809 (1989). Crossref, Web of Science, Google Scholar
F. Blanchet-Sadri, Semigroup Forum 47, 305 (1993). Crossref, Web of Science, Google Scholar
F. Blanchet-Sadri, Theoret. Comput. Sci. 123, 239 (1994). Crossref, Web of Science, Google Scholar
S. Eilenberg , Automata, Languages and Machines B ( Academic Press , 1976 ) . Google Scholar
S. Eilenberg and M. P. Schützenberger, Adv. Math. 19, 413 (1976). Crossref, Web of Science, Google Scholar
K. Henckell and J.-E. Pin, Algorithmic Problems in Groups and Semigroups, eds. J.-C. Birgetet al. (Birkhäuser, 2000) pp. 121–137. Crossref, Google Scholar
P. Higgins, Theoret. Comput. Sci. 178, 257 (1997). Crossref, Web of Science, Google Scholar
J-E. Pin, RAIRO Informatique Théorique 18, 23 (1984). Crossref, Web of Science, Google Scholar
J-E. Pin, Variétés de Langages Formels (Masson, 1984)(in French); English translation Varieties of Formal Languages (North Oxford Academic, 1986 and Plenum, 1986) . Google Scholar
J. Rhodes, Fac. Sci. Paris 23(10), 1 (1970). Google Scholar
M. V. Sapir, Problems of Burnside type and the finite basis property in varieties of semigroups, Izv. Akad. Nauk SSSR, Ser. Mat. 51 (1987) 319–340 (in Russian); English translation Math. USSR-Izv. 30 (1988) 295–314 . Google Scholar
I. Simon, Hierarchies of events of dot-depth one, Ph.D. thesis, University of Waterloo (1972) . Google Scholar
I. Simon, Proc. 2nd GI Conf., Lecture Notes in Computer Science 33 (Springer-Verlag, 1975) pp. 214–222. Crossref, Google Scholar
J. Stern, Theoret. Comput. Sci. 35, 17 (1985). Crossref, Web of Science, Google Scholar
H. Straubing, Semigroup Forum 19, 107 (1980). Crossref, Web of Science, Google Scholar
H. Straubing and D. Thérien, J. Algebra 119, 393 (1988). Crossref, Web of Science, Google Scholar
A. V. Tishchenko, Semigroup Forum 20, 171 (1980). Crossref, Web of Science, Google Scholar
M. V. Volkov, On finite basedness of semigroup varieties, Mat. Zametki 45(3) (1989) 12–23 (in Russian); English translation Math. Notes 45 (1989) 187–194 . Google Scholar
M. V. Volkov, Sci. Math. Jpn. 53, 171 (2001). Web of Science, Google Scholar
M. V. Volkov and I. A. Goldberg, Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory, Surikaisekikenkyusho Kokyuroku 1366 (Research Institute for Mathematical Sciences, Kyoto University, 2004) pp. 205–214. Google Scholar