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

DOI10.1007/S00233-010-9247-9MaRDI QIDQ5962338zbMATH OpenOpenAlexFDO

Authors Susan Hermiller, Steven Lindblad, J. C. Meakin

Publication date 22 September 2010

Published in Semigroup Forum (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1761434 (Why is no real title available?)
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• A topological approach to inverse and regular semigroups.
• Free Inverse Semigroups
• Groups and semigroups: connections and contrasts.
• Inverse monoids and rational subsets of related groups
• On one-relator monoids and one-relator groups
• Presentations of inverse monoids
• The word problem of inverse monoids presented by one idempotent relator

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)