The word problem of inverse monoids presented by one idempotent relator (Q1314383): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of some extended word problems defined by cancellation rules / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3859267 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cancellation rules and extended word problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5592246 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3853827 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inverse Monoids, Trees, and Context-Free Languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Free Inverse Semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3337662 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Presentations of inverse monoids / rank | |||
Normal rank |
Latest revision as of 13:04, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The word problem of inverse monoids presented by one idempotent relator |
scientific article |
Statements
The word problem of inverse monoids presented by one idempotent relator (English)
0 references
27 March 1994
0 references
The paper studies inverse semigroups presented by a finite set of generators \(X \cup X^{-1}\) and one relation \(e = 1\), where \(e\) represents an idempotent in the free inverse monoid, and 1 is the empty word. The word problem for inverse monoids is generally undecidable, but here the automaton approach of Stephen is used to prove that the decidability problem for words \(u\), \(v\) has complexity bounded by a cubic polynomial on the sum of the lengths of \(u\), \(v\) and \(e\), (if \(e\) is positively labelled, meaning that every vertex of its Munn tree is in \(X^*\), the complexity of the problem is linear). Moreover, it is shown that the set of words in the congruence class (in the free monoid) of \(u\) is a deterministic context-free language.
0 references
inverse semigroups
0 references
generators
0 references
idempotent
0 references
free inverse monoid
0 references
word problem
0 references
automaton
0 references
complexity
0 references
Munn tree
0 references
deterministic context-free language
0 references