Propositional Dynamic Logic with Program Costs
cs.LO, math.LO
Submitted: 2026-11-02
Updated: 2026-11-02
License: http://creativecommons.org/licenses/by/4.0/
The gist: We introduce N, a resource-aware variant of Propositional Dynamic Logic capable of accounting for program costs measured by natural numbers (such as time or space in the sense of computability…
Terminology
Abstract
We introduce N, a resource-aware variant of Propositional Dynamic Logic capable of accounting for program costs measured by natural numbers (such as time or space in the sense of computability theory). In this framework, programs correspond to transition systems weighted by extended natural numbers, and the syntax of our logic includes formulas expressing which properties are reachable by program executions within specific cost constraints. First, we explain how the standard program constructs of non-deterministic choice, sequential composition, iteration, and tests are interpreted in this weighted setting and establish the validity of their corresponding reduction axioms. Using an appropriate adaptation of the (Fischer-Ladner) filtration technique, we proceed to prove decidability and completeness for N as our main results. We furthermore provide upper and lower complexity bounds for this logic using translations between standard and N.
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring