Axiomatizations and Computability of Weighted Monadic Second-Order Logic
Abstract
Weighted monadic second-order logic is a weighted extension of monadic second-order logic that captures exactly the behaviour of weighted automata. Its semantics is parameterized with respect to a semiring on which the values that weighted formulas output are evaluated. Gastin and Monmege (2018) gave abstract semantics for a version of weighted monadic second-order logic to give a more general and modular proof of the equivalence of the logic with weighted automata. We focus on the abstract semantics of the logic and we give a complete axiomatization both for the full logic and for a fragment without general sum, thus giving a more fine-grained understanding of the logic. We discuss how common decision problems for logical languages can be adapted to the weighted setting, and show that many of these are decidable, though they inherit bad complexity from the underlying first- and second-order logics. However, we show that a weighted adaptation of satisfiability is undecidable for the logic when one uses the abstract interpretation.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- First-Order AutomataLuca Geatti, Alessandro Gianola, Nicola GiganteAAAI 2025 · 3 citations
- Weighted NetKAT: A Programming Language for Quantitative Network VerificationEmmanuel Suárez Acevedo, Tiago Ferreira, Kevin Batz, Oliver Bøving et al.PLDI 2026 · 1 citation
- Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form FormulaSagar Malhotra, Luciano SerafiniAAAI 2022 · 9 citations
- Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted AutomataIsmaël Jecker, Filip Mazowiecki, David PurserLICS 2024 · 4 citations
- EREQ: Regular Expressions with Quantifiers and Incremental Quantifier EliminationEkaterina Zhuchko, Ian Erik Varatalu, Margus Veanes, Nikolaj S. BjørnerPLDI 2026
