THE WORD PROBLEM FOR INVERSE MONOIDS PRESENTED BY ONE IDEMPOTENT RELATOR

被引：16

作者：

BIRGET, JC ^{[1
]}

MARGOLIS, SW ^{[1
]}

MEAKIN, JC ^{[1
]}

机构：

[1] UNIV NEBRASKA,DEPT MATH & STAT,LINCOLN,NE 68588

来源：

THEORETICAL COMPUTER SCIENCE | 1994年 / 123卷 / 02期

关键词：

D O I：

10.1016/0304-3975(92)00063-W

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：273 / 289

页数：17

共 11 条

[1]

Barwise J., 1977, HDB MATH LOGIC

[2] ON THE COMPLEXITY OF SOME EXTENDED WORD-PROBLEMS DEFINED BY CANCELLATION RULES [J].

BENOIS, M ;

SAKAROVITCH, J .

INFORMATION PROCESSING LETTERS, 1986, 23 (06) :281-287

[3]

Berstel J, 1979, TRANSDUCTIONS CONTEX

[4] CANCELLATION RULES AND EXTENDED WORD-PROBLEMS [J].

BOOK, RV ;

OTTO, F .

INFORMATION PROCESSING LETTERS, 1985, 20 (01) :5-11

[5]

Hopcroft J.E., 1979, INTRO AUTOMATA THEOR

[6]

LALLEMENT G, 1979, SEMIGROUPS COMBINATO

[7]

MARGOLIS SW, 1986, P LSU SEMIGROUP C LO, P37

[8]

MARGOLIS SW, IN PRESS T AMS

[9]

Munn W. D., 1974, P LOND MATH SOC, V30, P385

[10]

Petrich M., 1984, INVERSE SEMIGROUPS

← 1 2 →