Weighted restarting automata

In this work, we also extend weighted restarting automata to transducers. We prove that for weighted monotone restarting automata with auxiliary symbols, the variant that may keep on reading after performing a rewrite step (the so-called RRWW-automaton) is strictly more expressive than the variant that must restart immediately after performing a rewrite step (the so-called RWW-automaton), which again holds in the deterministic as well as in the nondeterministic case. This is the first time that a version of the monotone RRWW-automaton is shown to differ in expressive power from the corresponding version of the monotone RWW-automaton. Finally, we extend weighted restarting automata to language acceptors by adding an acceptance condition on the weight of its accepting computations. We will see that using such a relative acceptance, weighted restarting automata of a certain type coincide with the so-called non-forgetting restarting automata. In addition, another class of languages accepted by weighted restarting automata is shown to be closed under the operation of intersection. This is the first result that shows that a class of languages defined in terms of a quite general class of restarting automata is closed under the operation of intersection.