Name
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. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0304-3975(92)00063-W | Theor. Comput. Sci. |
Keywords | DocType | Volume |
word problem,idempotent relator,inverse monoids | Journal | 123 |
Issue | ISSN | Citations |
2 | Theoretical Computer Science | 5 |
PageRank | References | Authors |
0.50 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-Camille Birget | 1 | 815 | 59.09 |
| Stuart W. Margolis | 2 | 102 | 18.14 |
| John C. Meakin | 3 | 25 | 3.89 |