computation by commuting

55 Views Asked by At

I have some doubts about your paper Computing by commuting (abstract is copied below):

What do these sentences say (my REMARKS on what I do not follow are numbered by 1,2):

" the choice of a word to be catenated does not depend on the word erased, "

1.what does it mean that the word catenate does not depend on the word erased, do you have some example when it does depend on it ? i.e. it what sense it could depend on the word erased ? I would say that if if the catenation is not dependent then the situation is even more general than if it is not?

" If the deletion and the catenation are done arbitrarily at the opposite ends"

  1. what does it mean "arbitrarily" in that the deletion and catenation are done arbitrarily at the opposite ends ?

We consider the power of the following rewriting: given a finite or regular set X of words and an initial word w, apply iteratively the operation which deletes a word from X from one of the ends of w and simultaneously catenates another word from X to the opposite end of w. We show that if the deletion is always done at the beginning and the catenation at the end, and the choice of a word to be catenated does not depend on the word erased, then the generated language is always regular, though the derivability relation is not, in general, rational. If the deletion and the catenation are done arbitrarily at the opposite ends, the language need not be regular. If the catenation is done at the same end as the deletion, the relation of derivability is rational even if the catenated word can depend on the word erased.

1

There are 1 best solutions below

1
On BEST ANSWER
  1. I guess this is just to emphasize that you do not restrict to operations of the form $w \to (x^{-1}w)y$ with $y = x$.

  2. This means that two types of operations are allowed: $w \to (x^{-1}w)y$ and $w \to x(wy^{-1})$.