Non-looping string rewriting
Non-Looping String Rewriting
String rewriting reductions of the form , called , are the most frequent cause of infinite reductions (non- termination). Regarded as a model of computation, infinite reductions are unwanted whence their static detection is important. There are string rewriting systems which admit infinite reductions although they admit no loops. Their non-termination is particularly difficult to uncover. We present a few conditions for the existence of loops, and thus establish a means to recognize ...
Page 1