Lambda-confluence for context rewriting systems ?
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 ?, 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 ?-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 ? -confluence is decidable in polynomial time for limited context restarting automata of type R2 R 2 , but that this property is not even recursively enumerable for clearing restarting automata. The latter follows from the fact that ?-confluence is not recursively enumerable for finite factor-erasing string-rewriting systems.
context rewriting system ?-confluence factor-erasing string-rewriting system clearing restarting automaton limited context restarting automaton