Lune

LICS2021Top-tier venue

Axiomatizations and Computability of Weighted Monadic Second-Order Logic

Antonis Achilleos, Mathias Ruggaard Pedersen

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. First-Order AutomataLuca Geatti, Alessandro Gianola, Nicola GiganteAAAI 2025 · 3 citations
  2. 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
  3. Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form FormulaSagar Malhotra, Luciano SerafiniAAAI 2022 · 9 citations
  4. Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted AutomataIsmaël Jecker, Filip Mazowiecki, David PurserLICS 2024 · 4 citations
  5. EREQ: Regular Expressions with Quantifiers and Incremental Quantifier EliminationEkaterina Zhuchko, Ian Erik Varatalu, Margus Veanes, Nikolaj S. BjørnerPLDI 2026
Dusk over the sea between two cliffs drawn in fine vertical lines