The word problem for inverse monoids presented by one idempotent relator

Jean Camille Birget, Stuart W. Margolis, John C. Meakin

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

We study inverse monoids presented by a finite set of generators and one relation e = 1, where e is a word representing an idempotent in the free inverse monoid, and 1 is the empty word. We show that (1) the word problem is solvable by a polynomial-time algorithm; (2) every congruence class (in the free monoid) with respect to such a presentation is a deterministic context-free language. Such congruence classes can be viewed as generalizations of parenthesis languages; and (3) the word problem is solvable by a linear-time algorithm in the more special case where e is a "positively labeled" idempotent.

Original languageEnglish (US)
Pages (from-to)273-289
Number of pages17
JournalTheoretical Computer Science
Volume123
Issue number2
DOIs
StatePublished - Jan 31 1994

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The word problem for inverse monoids presented by one idempotent relator'. Together they form a unique fingerprint.

Cite this