Weighted Automata and Monadic Second Order Logic

Nadia Labai, Johann A. Makowsky

Let S be a commutative semiring. M. Droste and P. Gastin have introduced in 2005 weighted monadic second order logic WMSOL with weights in S. They use a syntactic fragment RMSOL of…