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