No Access

Reducibility vs. definability for pseudovarieties of semigroups

Departamento de Matemática, Faculdade de Ciências, Centro de Mathematica da Universidade do Porto, Rua do Campo Alegre, 687, 4169-007 Porto, Portugal

E-mail Address: jalmeida@fc.up.pt

Search for more papers by this author

and

O. Klíma

Department of Mathematics and Statistics, Masaryk University, Kotlářská 2, 611 37 Brno, Czech Republic

E-mail Address: klima@math.muni.cz

Search for more papers by this author

https://doi.org/10.1142/S0218196716500648Cited by:1 (Source: Crossref)

Abstract

It is easy to show that a pseudovariety which is reducible with respect to an implicit signature $σ$ $σ$ for the equation $x = y$ $x = y$ can also be defined by $σ$ $σ$ -identities. We present several negative examples for the converse using signatures in which the pseudovarieties are usually defined. An ordered example issue from the extended Straubing–Thérien hierarchy of regular languages is also shown to provide a positive example for the inequality $x \leq y$ $x \leq y$ .

Communicated by B. Steinberg

Keywords:

AMSC: Primary 20M07

References

1. D. Albert, R. Baldinger and J. Rhodes, The identity problem for finite semigroups (the undecidability of), J. Symbolic Logic 57 (1992) 179–192. Crossref, Web of Science, Google Scholar
2. J. Almeida, Finite Semigroups and Universal Algebra (World Scientific, Singapore, 1995). Link, Google Scholar
3. J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products, Int. J. Algebra Comput. 9 (1999) 241–261. Link, Web of Science, Google Scholar
4. J. Almeida, Dynamics of finite semigroups, in Semigroups, Algorithms, Automata and Languages eds. G. M. S. Gomes, J.-E. Pin and P. V. Silva (World Scientific, Singapore, 2002), pp. 269–292. Link, Google Scholar
5. J. Almeida, Profinite semigroups and applications, Structural Theory of Automata, Semigroups and Universal Algebra eds. V. B. Kudryavtsev and I. G. Rosenberg (Springer, New York, 2005), pp. 1–45. Crossref, Google Scholar
6. J. Almeida, J. C. Costa and M. Zeitoun, Complete reducibility of systems of equations with respect to R, Portugal. Math. 64 (2007) 445–508. Crossref, Google Scholar
7. J. Almeida, J. C. Costa and M. Zeitoun, Reducibility of pointlike problems, Semigroup Forum (2015), doi: 10.1007/s00233-015-9769-2. Crossref, Web of Science, Google Scholar
8. J. Almeida and M. Delgado, Tameness of the pseudovariety of abelian groups, Int. J. Algebra Comput. 15 (2005) 327–338. Link, Web of Science, Google Scholar
9. J. Almeida, S. Margolis, B. Steinberg and M. Volkov, Characterization of group radicals with an application to Mal’cev products, Ill. J. Math. 54 (2010) 199–221. Crossref, Web of Science, Google Scholar
10. J. Almeida and B. Steinberg, On the decidability of iterated semidirect products and applications to complexity, Proc. Lond. Math. Soc. 80 (2000) 50–74. Crossref, Web of Science, Google Scholar
11. J. Almeida and P. G. Trotter, The pseudoidentity problem and reducibility for completely regular semigroups, Bull. Aust. Math. Soc. 63 (2001) 407–433. Crossref, Web of Science, Google Scholar
12. J. Almeida and P. Weil, Profinite categories and semidirect products, J. Pure Appl. Algebra 123 (1998) 1–50. Crossref, Web of Science, Google Scholar
13. C. J. Ash, Inevitable graphs: A proof of the type II conjecture and some related decision procedures, Int. J. Algebra Comput. 1 (1991) 127–146. Link, Google Scholar
14. K. Auinger and B. Steinberg, On the extension problem for partial permutations, Proc. Am. Math. Soc. 131 (2003) 2693–2703. Crossref, Web of Science, Google Scholar
15. T. Bandman, G.-M. Greuel, F. Grunewald, B. Kunyavskiĭ, G. Pfister and E. Plotkin, Two-variable identities for finite solvable groups, C. R. Acad. Sci. Paris I Math. 337 (2003) 581–586. Crossref, Web of Science, Google Scholar
16. J. N. Bray, J. S. Wilson and R. A. Wilson, A characterization of finite soluble groups by laws in two variables, Bull. Lond. Math. Soc. 37 (2005) 179–186. Crossref, Web of Science, Google Scholar
17. J. C. Costa and C. Nogueira, Complete reducibility of the pseudovariety LSl . Int. J. Algebra Comput. 19 (2009) 247–282. Link, Web of Science, Google Scholar
18. S. Eilenberg, Automata, Languages and Machines, Vol. A (Academic Press, New York, 1974). Google Scholar
19. S. Eilenberg, Automata, Languages and Machines, Vol. B (Academic Press, New York, 1976). Google Scholar
20. J. Kad’ourek and L. Polák, On the word problem for free completely regular semigroups, Semigroup Forum 34 (1986) 127–138. Crossref, Web of Science, Google Scholar
21. M. Lothaire, Combinatorics on Words (Addison-Wesley, Reading, Mass., 1983). Google Scholar
22. V. A. Molchanov, Nonstandard characterization of pseudovarieties, Algebr. Univ. 33 (1995) 533–547. Crossref, Web of Science, Google Scholar
23. J.-E. Pin, Varieties of Formal Languages (Plenum, London, 1986). Crossref, Google Scholar
24. J.-E. Pin, Syntactic semigroups, Handbook of Formal Languages, eds. G. Rozenberg and A. Salomaa (Springer, New York, 1997). Crossref, Google Scholar
25. J.-E. Pin and P. Weil, A Reiterman theorem for pseudovarieties of finite first-order structures, Algebr. Univ. 35 (1996) 577–595. Crossref, Web of Science, Google Scholar
26. J.-E. Pin and P. Weil, Polynomial closure and unambiguous product, Theor. Comput. Syst. 30 (1997) 383–422. Crossref, Web of Science, Google Scholar
27. J. Reiterman, The Birkhoff theorem for finite algebras, Algebr. Univ. 14 (1982) 1–10. Crossref, Web of Science, Google Scholar
28. J. Rhodes and B. Steinberg, The q-theory of Finite Semigroups, Springer Monographs in Mathematics (Springer, New York, 2009). Crossref, Google Scholar