@UNPUBLISHED{OttMra15tcs,
  author = {Friedrich Otto and František Mráz},
  title = {Lambda-Confluence for Context Rewriting Systems},
  note = {Accepted for publication, in press, published on-line since 22.1.2015,
    http://dx.doi.org/10.1016/j.tcs.2015.01.013, impact factor 0.516},
  year = {2015},
  journal = {Theoretical Computer Science},
  owner = {František Mráz},
  timestamp = {2015.01.25},
  url = {http://dx.doi.org/10.1016/j.tcs.2015.01.013},
  abstract = {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 R2, 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.}
}