Abstract
We study a class of inverse monoids of the form M=Inv 〈X∣w=1〉, where the single relator w has a combinatorial property that we call sparse. For a sparse word w, we prove that the word problem for M is decidable. We also show that the set of words in (X∪X −1)* that represent the identity in M is a deterministic context free language, and that the set of geodesics in the Schützenberger graph of the identity of M is a regular language.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Birget, J.-C., Margolis, S.W., Meakin, J.C.: The word problem for inverse monoids presented by one idempotent relator. Theor. Comput. Sci. 123(2), 273–289 (1994)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Series in Computer Science. Addison-Wesley, Reading (1979)
Ivanov, S.V., Margolis, S.W., Meakin, J.C.: On one-relator inverse monoids and one-relator groups. J. Pure Appl. Algebra 159(1), 83–111 (2001)
Lawson, M.V.: Inverse Semigroups. World Scientific, River Edge (1998)
Lindblad, S.P.: Inverse monoids presented by a single sparse relator. PhD Thesis, Univ. of Nebraska-Lincoln (2003)
Margolis, S., Meakin, J., Šuniḱ, Z.: Distortion functions and the membership problem for submonoids of groups and monoids. Contemp. Math. 372, 109–129 (2005)
Meakin, J.C.: Groups and semigroups: connections and contrasts. In: Proceedings, Groups St Andrews 2005, London Math. Soc. Lecture Note Series 340, vol. 2, pp. 357–400 (2007)
Munn, W.D.: Free inverse semigroups. Proc. Lond. Math. Soc. 29(3), 385–404 (1974)
Stephen, J.B.: Presentations of inverse monoids. J. Pure Appl. Algebra 63(1), 81–112 (1990)
Stephen, J.B.: Inverse monoids and rational subsets of related groups. Semigroup Forum 46(1), 98–108 (1993)
Steinberg, B.: A topological approach to inverse and regular semigroups. Pac. J. Math. 208(2), 367–396 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to the memory of Douglas Munn.
Rights and permissions
About this article
Cite this article
Hermiller, S., Lindblad, S. & Meakin, J. Decision problems for inverse monoids presented by a single sparse relator. Semigroup Forum 81, 128–144 (2010). https://doi.org/10.1007/s00233-010-9247-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00233-010-9247-9