Decision problems for inverse monoids presented by a single sparse relator.

DOI10.1007/S00233-010-9247-9zbMATH Open1208.20049arXiv0911.1484OpenAlexW1993637468MaRDI QIDQ5962338FDOQ5962338

Steven Lindblad, Susan Hermiller, J. C. Meakin

Publication date: 22 September 2010

Published in: Semigroup Forum (Search for Journal in Brave)

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 cup X^{-1})^* that represent the identity in M is a deterministic context free language, and that the set of geodesics in the Schutzenberger graph of the identity of M is a regular language.

Full work available at URL: https://arxiv.org/abs/0911.1484

Recommendations

• Inverse monoids: decidability and complexity of algebraic questions.
• The word problem of inverse monoids presented by one idempotent relator
• scientific article; zbMATH DE number 459339
• Mathematical Foundations of Computer Science 2005
• Presentations of inverse monoids

zbMATH Keywords

word problemregular languagesgenerators and relationsinverse monoidscontext free languagesSchützenberger graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Algebraic theory of languages and automata (68Q70) Free semigroups, generators and relations, word problems (20M05) Inverse semigroups (20M18) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Free Inverse Semigroups
• Presentations of inverse monoids
• A topological approach to inverse and regular semigroups.
• Inverse monoids and rational subsets of related groups
• Title not available (Why is that?)
• On one-relator monoids and one-relator groups
• The word problem of inverse monoids presented by one idempotent relator
• Groups and semigroups: connections and contrasts.

Cited In (7)

• A tribute to John Meakin on the occasion of his 75th birthday
• Solution of the membership problem of the prefix monoid in certain one-relator groups.
• The word problem for one-relation monoids: a survey
• Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs
• On one-relator groups and units of special one-relation inverse monoids
• Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups
• New results on the prefix membership problem for one-relator groups

This page was built for publication: Decision problems for inverse monoids presented by a single sparse relator.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962338)