Working Seminar on Formal Models, Discrete Structures, and Algorithms

A new acceptance modus for weighted finite automata

Werner Kuich (TU Wien)

When: March 19, 2:00pm

Where: room G2.91b/G215


Inspired by the acceptance modus for the weighted finite automata for quantitative languages (Chatterjee, Doyen, Henzinger: Quantitative languages.- LNCS 5213, 385 - 400, 2008) we let the weight of a path in the graph of such an automaton be dependent on the length of the path. (E. g., the weight of a path may be the average of the weight of its edges.) Summing up the weights of all paths from an initial to a final state gives then the behavior of such an automaton. For this acceptance modus, the theory of semiring - weighted finite automata is not applicable. But the algebraic theory of these weighted finite automata leads to weighted finite automata over hemirings (i. e., semirings without 1).

We develop a theory of Conway hemirings and show for weighted finite automata over Conway hemirings a Kleene Theorem that is applicable to the weighted finite automata with the new acceptance modus.