"Lambda-Confluence Is Undecidable for Clearing Restarting Automata" . "[B6AFE7F7C419]" . . . . "Lambda-Confluence Is Undecidable for Clearing Restarting Automata" . . "Mr\u00E1z, Franti\u0161ek" . "Lambda-Confluence Is Undecidable for Clearing Restarting Automata"@en . . "978-3-642-39273-3" . "0302-9743" . "Lambda-Confluence Is Undecidable for Clearing Restarting Automata"@en . . "RIV/00216208:11320/13:10145557" . "Berlin" . "Halifax, Kanada" . "84237" . "limited context restarting automaton; factor-erasing string-rewriting system; Clearing restarting automaton; lamda-confluence"@en . . "RIV/00216208:11320/13:10145557!RIV14-GA0-11320___" . . "Springer-Verlag" . . "2"^^ . "2013-07-16+02:00"^^ . . "1"^^ . . "Implementation and Application of Automata" . . . . "P(GAP103/10/0783)" . "Clearing restarting automata are based on contextual rewriting. A word w is accepted by an automaton of this type if there is a computation that reduces the word w to the empty word \u00CE}} by a finite sequence of rewritings. Accordingly, the word problem for a clearing restarting automaton can be solved nondeterministically in quadratic time. If, however, the contextual rewritings happen to be \u00CE}}-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, unfortunately, \u00CE}}-confluence is not even recursively enumerable for clearing restarting automata. This follows from the fact that \u00CE}}-confluence is not recursively enumerable for finite factor-erasing string-rewriting systems."@en . . "10.1007/978-3-642-39274-0_23" . "12"^^ . "Otto, Friedrich" . . "http://dx.doi.org/10.1007/978-3-642-39274-0_23" . . "Clearing restarting automata are based on contextual rewriting. A word w is accepted by an automaton of this type if there is a computation that reduces the word w to the empty word \u00CE}} by a finite sequence of rewritings. Accordingly, the word problem for a clearing restarting automaton can be solved nondeterministically in quadratic time. If, however, the contextual rewritings happen to be \u00CE}}-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, unfortunately, \u00CE}}-confluence is not even recursively enumerable for clearing restarting automata. This follows from the fact that \u00CE}}-confluence is not recursively enumerable for finite factor-erasing string-rewriting systems." . "11320" . .