×

The word problem for nilpotent inverse monoids. (English) Zbl 0838.20059

The author says that an inverse semigroup \(S\) is \(k\)-nilpotent if \(S\) has a zero and \(a^k=0\) for every non-idempotent \(a\in S\). Let \(N_k(X)\) denote the largest \(k\)-nilpotent Rees quotient of the free inverse monoid on the set \(X\). The author proves that, for every \(k\geq 1\) and for every finitely generated congruence \(\tau\) on \(N_k(X)\), the quotient monoid \(N_k(X)/\tau\) has decidable word problem and finite \({\mathcal D}\)-classes.

MSC:

20M05 Free semigroups, generators and relations, word problems
20M18 Inverse semigroups
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Berstel, J., ”Transductions and Context-free Languages,” B. G. Teubner, Stuttgart, 1979. · Zbl 0424.68040
[2] Eilenberg, S., ”Automata, languages and machines (vol. A),” Academic Press, New York, 1974. · Zbl 0317.94045
[3] Hopcroft, J. E., and Ullman, J. D., ”Formal Languages and Their Relation to Automata,” Addison-Wesley, Reading, Mass., 1969. · Zbl 0196.01701
[4] Howie, J. M., ”An Introduction to Semigroup Theory,” Academic Press, London, 1976. · Zbl 0355.20056
[5] Lothaire, M., ”Combinatorics on Words,” Addison-Wesley, Reading, Mass., 1983. · Zbl 0514.20045
[6] Margolis, S. W., and Meakin, J. C.,Inverse monoids, trees and context-free languages, Trans. Amer. Math. Soc. (1)335 (1993), 259–276. · Zbl 0795.20043 · doi:10.2307/2154268
[7] Munn, W. D.,Free inverse semigroups, Proc. London Math. Soc. (3)29 (1974), 385–404. · Zbl 0305.20033 · doi:10.1112/plms/s3-29.3.385
[8] Munn, W. D., and Reilly, N. R.,E-unitary congruences on inverse semigroups, Glasgow Math. J.17 (1976), 57–75. · Zbl 0328.20048 · doi:10.1017/S0017089500002731
[9] Petrich, M., ”Inverse semigroups,” Wiley, New York, 1984. · Zbl 0546.20053
[10] Scheiblich, H. E.,Free inverse semigroups, Proc. Amer. Math. Soc.38 (1973), 1–7. · Zbl 0256.20079 · doi:10.1090/S0002-9939-1973-0310093-1
[11] Silva, P. V.,Rational languages and inverse monoid presentations, Int. J. Alg. Comp.2.2 (1992), 187–207. · Zbl 0777.20023 · doi:10.1142/S0218196792000128
[12] Stephen, J. B.,Presentations of inverse monoids, J. Pure Appl. Alg.63 (1990), 81–112. · Zbl 0691.20044 · doi:10.1016/0022-4049(90)90057-O
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.