Author's: Laurent Poinsot, Gérard H. E. Duchamp and Christophe Tollu
Pages: [265] - [285]
Received Date: May 28, 2010
Submitted by:
A partial monoid P is a set with a partial multiplication
(and total identity
), which satisfies some associativity axiom.
The partial monoid P may be embedded in the free monoid
and the product
is simulated by a string rewriting system on
that consists in evaluating the
concatenation of two letters as a product in P, when it is
defined, and a letter
as the empty word
In this paper, we study the profound
relations between confluence for such a system and associativity of
the multiplication. Moreover, we develop a reduction strategy to
ensure confluence, and which allows us to define a multiplication on
normal forms associative up to a given congruence of
Finally, we show that this operation is
associative, if and only if, the rewriting system under consideration
is confluent.
partial monoid, string rewriting system, normal form, associativity and confluence.