V. E.
CĂZĂNESCU
Foundation of the Rewriting in an Algebra
Abstract. This paper includes two main ideas. The first one, rewriting in
an algebra, was introduced in [5]. The second one, boolean rewriting, can be
found in many papers but we were never able to find a clear comparison with the
classic one. We prefer rewriting in an algebra to term rewriting. This is our
way to give a unique theory of rewriting. If the algebra is free, then we get
the term rewriting. If the algebra is a certain quotient of a free algebra then
we get rewriting modulo equations. Rewriting is said to be boolean when the
condition of each conditional equation is of boolean sort
(in the free algebra it is a boolean term). We prove the classic rewriting is
equivalent to boolean rewriting in a specific algebra, therefore, boolean
rewriting is more general than the classic one.
READ THE PDF |