On the Noetherian Properties of Reduction System of Words

Abstract

For any set of symbols, denotes the set of all words of symbols over , including the empty string . The set denotes the free monoid generated by under the operation of concatenation with the empty string serving as identity. Let R be a nite set. We de ne the binary relation )R as follows, where u; v 2 : u)R v if there exist x; y 2 and (l;m) 2 R with u = xly and v = xmy. The structure

;)R

is a reduction system of words and the relation )R is the reduction relation. Let

;)R

be a reduction system of words. The relation )R is Noetherian if there is no in nite sequence w0;w1; ::: 2 such that for all i 0;wi)R wi+1. In this paper, we study properties of reduction systems of words and give conditions under which a reduction system of word is Noetherian.