Weighted Timed MSO Logics

Karin Quaas

Abstract:
We aim to generalize Büchi's fundamental theorem on the coincidence of recognizable and MSO-definable languages to the weighted timed setting. For this, we investigate subclasses of weighted timed automata and show how we can extend existing timed MSO logics with weights. Here, we focus on the class of weighted event-recording automata as well as a weighted extension of the full logic MSOer(Sigma) introduced by D'Souza. We show that every weighted event-recording automaton can effectively be transformed into a corresponding sentence of our logic and vice versa. The methods presented in the paper can be adopted to weighted versions of timed automata and Wilke's logic of relative distance. The results indicate the robustness of weighted timed automata models and may be used for specification purposes.