Abstrakt
Clearing restarting automata and limited context restarting automata are particular types of context rewriting systems. A word w is accepted by such a system if there is a sequence of rewritings that reduces the word w to the empty word lambda, where each rewrite rule is extended by certain context conditions.
If each rewrite step is strictly length-reducing, as for example in the case of clearing restarting automata, then the word problem for such a system can be solved nondeterministically in quadratic time. If, in addition, the contextual rewritings happen to be lambda-confluent, that is, confluent on the congruence class of the empty word, then the word problem can be solved deterministically in linear time.
Here we show that lambda-confluence is decidable in polynomial time for limited context restarting automata of type R-2, but that this property is not even recursively enumerable for clearing restarting automata. The latter follows from the fact that lambda-confluence is not recursively enumerable for finite factor-erasing string-rewriting systems. (C) 2015 Elsevier B.V.
All rights reserved.