Weighted restarting automata and pushdown relations

作者：Wang Qichao^*; Otto Friedrich

来源：Theoretical Computer Science, 2016, 635: 1-15.

DOI：10.1016/j.tcs.2016.04.038

• Weighted restarting automaton
• Restarting transducer
• Pushdown relation
• Almost-realtime pushdown relation

Weighted restarting automata have been introduced to study quantitative aspects of computations of restarting automata. Here we study the special case that words over a given (output) alphabet are assigned as weights to the transitions of a restarting automaton. In this way the automaton is extended to define a mapping from the words over its input alphabet into the semiring of formal languages over a given (output) alphabet, generalizing the restarting transducers introduced by Hundeshagen (2013) [7]. We establish that the monotone restarting transducers that are allowed to use auxiliary symbols characterize the class of almost-realtime pushdown relations, and we characterize the deterministic pushdown functions by a particular type of deterministic monotone restarting transducer. Further, we show that already linearly bounded (word-)weighted monotone restarting automata that use auxiliary symbols are more expressive than the corresponding restarting transducers, both in the deterministic as well as in the nondeterministic case. Finally, we prove that for (word-)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.

• 出版日期2016-7-4