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

context free languagesgenerators and relationsinverse monoidsregular languagesSchützenberger graphsword problem

Mathematics Subject Classification ID

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

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.

Review text

The main result of this paper asserts that the word problem is decidable for the quotient of the free inverse monoid modulo one relation having a certain combinatorial property, which the authors call `sparse' (roughly speaking, if a word \(w\) is sparse, then distinct occurrences of prefixes and suffixes of \(w\) that occur elsewhere as cyclic subwords of \(w\) are separated by at least one letter). Additionally to the main result, it is shown that the set of words representing the identity in this quotient monoid is a deterministic context free language, and that the set of geodesics in the Schützenberger graph of the identity in this quotient monoid 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

• A topological approach to inverse and regular semigroups.
• Free Inverse Semigroups
• Groups and semigroups: connections and contrasts.
• 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?)
• 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

(8)

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

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)