Publication at Faculty of Mathematics and Physics |
2017
Abstract
In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the tape contents is reduced to a particular word within a finite number of applications of these contextual rewritings.
Here we extend the limited context restarting automata by using additional global means to structure the reductions they execute. In fact, we study regulated lc-R-automata, for which a regular control language is used to restrict the set of admissible reduction sequences, and we propose random context conditions to restrict the place at which a transition of an lc-R-automaton can be applied.