Decision problems for inverse monoids presented by a single sparse relator. (Q5962338): Difference between revisions

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.