2015/06/19 by Manfred Droste, Vitaly Perevoshchikov · 2 citations
Computer Science · #cs.FL #cs.LO
paper · pdf · doi:10.1007/978-3-642-38536-0_36
The final version appeared in the Proceedings of the 8th International Computer Science Symposium in Russia (CSR 2013)
arxiv created 2015/06/19 · arxiv updated 2015/06/22
Weighted automata are non-deterministic automata where the transitions are equipped with weights. They can model quantitative aspects of systems like costs or energy consumption. The value of a run can be computed, for example, as the maximum, limit average, or discounted sum of transition weights. In multi-weighted automata, transitions carry several weights and can model, for example, the ratio between rewards and costs, or the efficiency of use of a primary resource under some upper bound constraint on a secondary resource. Here, we introduce a general model for multi-weighted automata as well as a multiweighted MSO logic. In our main results, we show that this multi-weighted MSO logic and multi-weighted automata are expressively equivalent both for finite and infinite words. The translation process is effective, leading to decidability results for our multi-weighted MSO logic.