TY - JOUR

T1 - The word problem for inverse monoids presented by one idempotent relator

AU - Birget, Jean Camille

AU - Margolis, Stuart W.

AU - Meakin, John C.

N1 - Funding Information:
Correspondence to: J.-C. Birget, Department Nebraska, Lincoln, NE 68588, USA * Research supported by N.S.F. Grant No. Information Sciences, University of Nebraska,

PY - 1994/1/31

Y1 - 1994/1/31

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028274465&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028274465&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(92)00063-W

DO - 10.1016/0304-3975(92)00063-W

M3 - Article

AN - SCOPUS:0028274465

VL - 123

SP - 273

EP - 289

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 2

ER -