Weighted Restarting Automata

Restarting automata have been introduced as a formal tool to model the analysis by reduction, which is a technique used in linguistics to analyse sentences of natural languages. A restarting automaton M is a language accepting device: Given an input word w over some input alphabet S, it either accepts or rejects. But in case of acceptance, one may be interested in the number of accepting computations of M on input w, or one may be interested in the least number of steps (or cycles) in such an accepting computation. For answering such quantitative questions, we introduce the concept of a weighted restarting automaton. Such an automaton is defined as a pair (M, ¿), where M is a restarting automaton of type X on some input alphabet S, and ¿ is a weight function from the transitions of M into a semiring S. In this way, a weighted restarting automaton (M, ¿) can represent a function fM ¿ from S* into S. We show some syntactic and semantic properties of these functions such as upper bounds (see [BFGM05]), growth rates and closure properties. 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. von Wang, Qichao