Speaker Affiliation :
Date(s) - 04/02/2016
11 h 00 min - 12 h 00 min
SÉMINAIRE COMMUN I2M (LDP) – LIF (MOVE)
This talk will present some of the recent results obtained in the community on the relationship between weighted automata and weighted logics. The story started 10 years ago with the introduction of a quantitative semantics for MSO logic over words and an equivalence theorem between weighted automata and a restricted weighted MSO logic. Since then, many extensions have been studied: from words to trees, infinite words, pictures, etc; from semirings to more general weight computations. Also, the proof techniques have matured, from low level, carefully mimicking the classical proofs in the boolean setting, to higher level, using various abstract semantics. We illustrate this evolution by introducing a core weighted logic and its abstract semantics as multisets of weight structures. The equivalence between weighted automata and core weighted logic holds at the level of the abstract semantics. We will also demonstrate the versatility of the weighted automata approach by instantiating it into the transducer setting, showing a possible lead towards the design of an alternative logic for transductions.