Weighted automata and weighted logics with discounting |
| |
Authors: | Manfred Droste George Rahonis |
| |
Affiliation: | 1. Institute of Computer Science, Leipzig University, D-04009 Leipzig, Germany;2. Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece |
| |
Abstract: | We introduce a weighted logic with discounting and we establish the Büchi–Elgot theorem for weighted automata over finite words and arbitrary commutative semirings. Then we investigate Büchi and Muller automata with discounting over the max-plus and the min-plus semiring. We show their expressive equivalence with weighted MSO-sentences with discounting. In this case our logic has a purely syntactic definition. For the finite case, we obtain a purely syntactically defined weighted logic if the underlying semiring is additively locally finite. |
| |
Keywords: | Weighted automata Weighted Bü chi and Muller automata Formal power series Weighted MSO logic Discounting |
本文献已被 ScienceDirect 等数据库收录! |