betaFeedback

WorksComputer Science

Propositional Dynamic Logic with Program Costs

Abstract

We introduce NPDL\mathbb{N}\mathtt{PDL}, a resource-aware variant of Propositional Dynamic Logic (PDL\mathtt{PDL}) 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 NPDL\mathbb{N}\mathtt{PDL} as our main results. We furthermore provide upper and lower complexity bounds for this logic using translations between standard PDL\mathtt{PDL} and NPDL\mathbb{N}\mathtt{PDL}.

Introduction

In the landscape of formal methods in computer science, Propositional Dynamic Logic (PDL) is a well-known logical calculus for reasoning about programs to formally verify their correctness [6, 10]. Combining modal logic and regular expressions, PDL specifies operational program constructs such as non-deterministic choice, sequential composition, iteration, and tests in a decidable logical framework. More broadly, PDL can be conceived as a prototypical logic of ‘action and consequence’. For instance, this has been a primary inspiration for the ‘dynamic turn’ in epistemic logic [23], where PDL and extensions thereof have been used to model concepts such as belief revision [24] or communicative updates [22].

While standard PDL describes the qualitative reachability of states, in practice one may require additional quantitative assessments. In the computational context, systems have critical constraints on resources such as time, memory, or energy. Therefore, it is reasonable to consider formal frameworks capable of reasoning about program efficiency. Similar motivations arise in other areas, for instance due to the fact that actions of real-world agents are driven by considerations of cost and utility. In this article we introduce NPDL, a logic which includes discrete program costs (e.g. time or space in the sense of computability theory) into the PDL framework.

Here, programs π\pi correspond to weighted accessibility relations Rπ:X2→N∞R_{\pi}: X^{2} \to\mathbb{N}_{\infty}, where the weight Rπ(x,y)R_{\pi}(x,y) is an extended natural number modeling the (least) cost of reaching yy via executing π\pi at xx. In particular, the addition of natural numbers is seen as cost combination and the weights 00 and ∞\infty correspond to the usual accessibility and inaccessibility of PDL. From this perspective, the weighted program constructs such as composition and iteration we define for NPDL are chosen to naturally generalize those of standard PDL (Subsection 2.1).

The syntax of NPDL includes formulas ⟨π⟩≤mφ\langle\pi\rangle^{\leq m}\varphi for every (non-extended) natural number m∈Nm \in\mathbb{N}, intuitively stating that ‘executing π\pi to reach φ\varphi is possible for a cost of no more than mm’. That is, the ‘base logic’ underlying NPDL is similar to weighted/chain-graded modal logic [12, 5, 15]. In the language of NPDL, various

Key words and phrases. PDL, Weighted Graphs, Program Cost, Decidability, Completeness. cost-sensitive properties of programs are easily expressible, for instance φ→[π]∗mφ\varphi\to[\pi]^{*m}\varphi can be read as ‘φ\varphi is preserved while looping π\pi without exceeding cost mm’. Validities, for example of reduction axioms for weighted program constructs, can express program equivalences up to a cost (Subsection 2.2).

As the main results of this article, we prove decidability (Section 3) and completeness (Section 4) for NPDL. Based on the above-mentioned reduction axioms, we define an adequate notion of Fischer-Ladner closure FL(φ)FL(\varphi) for every formula φ\varphi. The size ∣FL(φ)∣|FL(\varphi)| remains finite with upper bound ∥φ∥N∈N\|\varphi\|_{\mathbb{N}} \in\mathbb{N} parametric in φ\varphi, however this bound can be strictly larger than the length of φ\varphi (Subsection 3.1). We then define appropriate (weighted) filtrations and prove the corresponding Filtration Theorem, showing that NPDL has the bounded finite model property1 (Subsection 3.2). To obtain decidability we also show that verifying satisfiability of φ\varphi it suffices to restrict to models with bounded weights at most N(φ)+1∈NN(\varphi)+1 \in\mathbb{N}, again parametric in φ\varphi (Subsection 3.3). Using Fischer-Ladner filtrations of quasi-canonical models, we prove that the reduction axioms of NPDL together with weighted generalizations of the induction rule yield a sound and (weakly) complete axiomatization (Section 4). While our proofs are based on standard techniques (e.g. see [10]), the addition of costs presents additional technical challenges, which for instance becomes apparent in the proof of the Filtration Theorem (Theorems 3.7 & 4.6), the novel use of ‘cut-off models’ (Subsection 3.3), or the proof that the quasi-canonical model is standard with respect to sequential composition (Proposition 4.4(2)).

To obtain a 2EXPTIME-upper bound on the complexity of NPDL, we use a translation of NPDL into standard PDL over an extended set of atomic programs (Subsection 5.1). This translation is interesting in its own right, as it illustrates that NPDL is more succinct than standard PDL. This is also apparent in the complexity of the model checking problem (Subsection 5.2). The question whether NPDL remains EXPTIME-complete is left as the main open problem. More details and further questions for future research (e.g. interpolation, generalizations to other logics) are found in the concluding Section 6.

Related Work. Other cost-sensitive versions of PDL have been proposed in the literature [3, 20, 21], however all of these are fuzzy or many-valued (i.e. formulas can receive non-classical truth-values). While we retain the representation of costs via weighted accessibility relations used therein, note that in NPDL formulas remain Boolean-valued. In this sense, our setting more closely resembles that of graded-belief based programs in [13, 14], though these works are otherwise dissimilar in their motivation, set-up, and results. As mentioned above, the (non-dynamic) modal logic underlying NPDL is similar to weighted modal logic [12, 5] (which often uses real weights) and finite-chain graded modal logic [15] (note that this differs from the ‘graded modal logic’ which counts successors). For instance, it is straightforward to adapt our filtration method to obtain decidability for the latter. Lastly, let us mention [9], which proves strong completeness of iteration-free chain-graded PDL as an instance of a coalgebraic dynamic logic [8] (cf. Remark 2.5).

In this section, we explain how to interpret costs on frames weighted by extended natural numbers (Subsection 2.1) and introduce PDL with program costs (Subsection 2.2). Throughout the paper, we assume that the reader is familiar with basic modal logic and standard propositional dynamic logic (e.g. see [1, 10]).

Extended Natural Numbers and Cost Frames

2.1. Extended Natural Numbers and Cost Frames. We exclusively deal with discrete costs modeled by extended natural numbers N∞:=N∪{∞}\mathbb{N}^{\infty} := \mathbb{N} \cup\{\infty\}, where the value ∞\infty is intuitively interpreted as an ‘unattainable’ cost corresponding to inaccessibility. We often think of the extended natural numbers as endowed with the tropical semiring (respectively quantale) structure ⟨N∞,∧,+,∞,0⟩\langle\mathbb{N}^{\infty}, \wedge, +, \infty, 0\rangle where ∧\wedge is the minimum (which defines a complete lattice order, in particular ⋀∅=∞\bigwedge\varnothing= \infty) and ++ is addition of natural numbers with ∞\infty absorbing (i.e. x+∞=∞+x=∞x + \infty= \infty+ x = \infty). We intuitively think of addition as cost combination (other notions of cost combination can also be accommodated, see Remark 2.4).

While semantics of standard modal logic (and PDL) is based on Kripke frames (i.e. directed graphs), we use weighted directed graphs for our underlying semantics.

Definition 2.1 (Cost frames). A cost frame ⟨X,R⟩\langle X, R\rangle consists of a set of states XX together with a weighted accessibility relation R:X2→N∞R: X^2 \to\mathbb{N}^{\infty}.

The value R(x,y)∈N∞R(x,y) \in\mathbb{N}^{\infty} models the (least) cost of the RR-transition from xx to yy. In particular, every Kripke frame R⊆X2R \subseteq X^2 can be naturally seen as a cost frame via R(x,y)=0⇔xRyR(x,y) = 0 \Leftrightarrow xRy and R(x,y)=∞⇔¬xRyR(x,y) = \infty\Leftrightarrow\neg xRy. That is, cost 00 represents standard accessibility (i.e. ‘for free’) and cost ∞\infty represents standard inaccessibility (i.e. ‘never affordable’). This idea, albeit simple, guides many of our considerations in this article. For instance, the following generalizes the usual composition of binary relations in this sense.

Definition 2.2 (Sequential composition). Let ⟨X,R1⟩\langle X, R_1\rangle and ⟨X,R2⟩\langle X, R_2\rangle be cost frames. The sequential composition of R1R_1 and R2R_2 is the weighted relation R1∘R2:X2→N∞R_1 \circ R_2: X^2 \to\mathbb{N}^{\infty} defined by

(R1∘R2)(x,y)=⋀v∈XR1(x,v)+R2(v,y).(R_1 \circ R_2)(x,y) = \bigwedge_{v \in X} R_1(x,v) + R_2(v,y).

That is, R1∘R2(x,y)R_1 \circ R_2(x,y) represents the least cost to get from xx to yy by an R1R_1-transition followed by an R2R_2-transition (where ++ corresponds to cost combination). Similarly, we generalize reflexive transitive closures. For any subset S⊆XS \subseteq X, define the diagonal ΔS:X2→N∞\Delta_S: X^2 \to\mathbb{N}^{\infty} by

ΔS(x,y)={0if x=y&x∈S,∞otherwise.\Delta_S(x,y) = \begin{cases} 0 & \text{if } x = y \mathrel{\&} x \in S,\\ \infty& \text{otherwise.} \end{cases}

Definition 2.3 (Iteration). For ⟨X,R⟩\langle X, R\rangle a cost frame, inductively define R[k]:X2→N∞R^{[k]}: X^2 \to\mathbb{N}^{\infty} for all k≥0k \geq0 by R[0]=ΔXR^{[0]} = \Delta_X and R[k+1]=R∘R[k]R^{[k+1]} = R \circ R^{[k]}. The iteration R∗:X2→N∞R^*: X^2 \to\mathbb{N}^{\infty} is defined by

R∗(x,y)=⋀k≥0R[k](x,y).R^*(x,y) = \bigwedge_{k \geq0} R^{[k]}(x,y).

Remark 2.4 (Other cost combinations). Our definitions are based on the tropical semiring structure on N∞\mathbb{N}^{\infty}, however one can develop similar frameworks for other quantales. For instance, one may consider ⟨N∞,∧,∨,∞,0⟩\langle\mathbb{N}^{\infty}, \wedge, \vee, \infty, 0\rangle, instead treating the maximum ∨\vee as cost combination (e.g. , while ++ as combination is reasonable for interpreting cost as time, using ∨\vee as combination appears more reasonable for interpreting cost as space). In this article, we focus on the (technically more challenging) case of ++, however let us note that most of our results have analogues (oftentimes simpler) in the case of ∨\vee.

Remark 2.5 (Coalgebraic perspective [8, 9]). Besides their cost interpretation, the above operations on cost frames arise naturally from a coalgebraic perspective. That is, weighted cost frames can be identified with P∞\mathcal{P}_{\infty}-coalgebras where P∞:X↦(N∞)X\mathcal{P}_{\infty}: X \mapsto(\mathbb{N}^{\infty})^X is an appropriate generalization of the covariant powerset functor P\mathcal{P} (whose coalgebras are standard Kripke frames). It can be checked (cf. [9 Example 10(2)]) that this functor is a monad, the composition ∘\circ defined above is the corresponding Kleisli composition, and (⋅)∗(\cdot)^* can be seen as Kleisli iteration (in particular noting that Δ\Delta relates to the unit of the monad PN∞\mathcal{P}_{\mathbb{N}^{\infty}}).

Syntax and Semantics

We now introduce NPDL, our cost-sensitive variant of PDL, in the following language.

Definition 2.6 (Formulas & Programs). We define the collections of formulas φ∈Φ\varphi\in\Phi and programs π∈Π\pi\in\Pi by simultaneous induction as follows.

φ::=p∣¬φ∣φ1∧φ2∣⟨π⟩mφπ::=a∣π1∪π2∣π1;π2∣π∗∣ψ?\begin{aligned} \varphi&::= p \mid\neg\varphi\mid\varphi_1 \wedge\varphi_2 \mid\langle\pi\rangle^{m}\varphi\\ \pi&::= a \mid\pi_1 \cup\pi_2 \mid\pi_1;\pi_2 \mid\pi^* \mid\psi? \end{aligned}

Here, p∈Φ0p \in\Phi_0 and a∈Π0a \in\Pi_0 range over countable collections of propositional variables and atomic programs, respectively, and m∈Nm \in\mathbb{N} ranges over the (non-extended) natural numbers.

We define additional propositional connectives such as ∨,→,⊤,⊥\lor, \to, \top, \bot as usual and we use [π]mφ:=¬⟨π⟩m¬φ[\pi]^m\varphi:= \neg\langle\pi\rangle^m\neg\varphi. As in standard PDL we refer to the program constructs ∪\cup as non-deterministic choice, ;; as sequential composition, and (⋅)∗(\cdot)^* as iteration. Programs of the form ψ?\psi? are called tests. For our semantics we assign cost frames (Definition 2.1) to programs.

Definition 2.7 (Models). A model is a structure M=⟨X,{Ra}a∈Π0,Val⟩\mathcal{M} = \langle X, \{R_a\}_{a\in\Pi_0}, \mathrm{Val}\rangle such that ⟨X,Ra⟩\langle X, R_a\rangle is a cost frame for every atomic program a∈Π0a \in\Pi_0 and Val:Φ0→P(X)\mathrm{Val}: \Phi_0 \to\mathcal{P}(X) is a propositional valuation.

References

  1. [1]Blackburn, P., de Rijke, M., and Venema, Y. Modal Logic, vol. 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2001.DOI
  2. [2]Borzechowski, M., Gattinger, M., Hansen, H., Ramanayake, R., Trucco Dalmas, V., and Venema, Y. Propositional dynamic logic has Craig interpolation: a tableau-based proof, 2025. Preprint.arxiv.org/abs/2503.13276
  3. [3]Běhounek, L. Modeling costs of program runs in fuzzified propositional dynamic logic. In Doktorandský den ’08 (2008), H. F., Ed., Matfyzpress, pp. 11–18.
  4. [4]Danecki, R. Nondeterministic propositional dynamic logic with intersection is decidable. In Computation Theory (1985), A. Skowron, Ed., vol. 208 of LNCS, Springer Berlin Heidelberg, pp. 34–53.DOI
  5. [5]Dong, H., Li, X., and Wáng, Y. Weighted modal logic in epistemic and deontic contexts. In Logic, Rationality, and Interaction (LORI’21) (2021), S. Ghosh and T. Icard, Eds., Springer International Publishing, pp. 73–87.DOI
  6. [6]Fischer, M., and Ladner, R. Propositional dynamic logic of regular programs. Journal of Computer and System Sciences 18, 2 (1979), 194–211.DOI
  7. [7]Floyd, R. Algorithm 97: Shortest path. Communications of the ACM 5, 6 (1962), 345–345.DOI
  8. [8]Hansen, H., and Kupke, C. Weak completeness of coalgebraic dynamic logics. In 10th International Workshop on Fixed Points in Computer Science (FICS’15) (2015), R. Matthes and M. Mio, Eds., vol. 191 of EPTCS, Open Publishing Association, pp. 90–104.
  9. [9]Hansen, H., and Poiger, W. Safety and strong completeness via reducibility for many-valued coalgebraic dynamic logics. In 11th Conference on Algebra and Coalgebra in Computer Science (CALCO’25) (2025), C. Cîrstea and A. Knapp, Eds., vol. 342 of LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 9:1–9:23.
  10. [10]Harel, D., Kozen, D., and Tiuryn, J. Dynamic Logic. Foundations of Computing. MIT Press, 2000.
  11. [11]Kloibhofer, J., Trucco Dalmas, V., and Venema, Y. Interpolation for converse PDL. In Automated Reasoning with Analytic Tableaux and Related Methods (2026), G. Pozzato and T. Uustalu, Eds., Springer, pp. 258–277.arxiv.org/abs/2508.21485
  12. [12]Larsen, K., and Mardare, R. Complete proof systems for weighted modal logic. Theoretical Computer Science 546 (2014), 164–175.DOI
  13. [13]Laverny, N., and Lang, J. From knowledge-based programs to graded belief-based programs, Part I: On-line reasoning. Synthese 147, 2 (2005), 277–321.
  14. [14]Laverny, N., and Lang, J. From knowledge-based programs to graded belief-based programs, Part II: Off-line reasoning. In 19th International Joint Conference on Artificial Intelligence (IJCAI’05) (2005), IJCAI, pp. 497–502.
  15. [15]Ma, M., and Wang, S. Finite-chain graded modal logic. In Modality, Semantics and Interpretations: The Second Asian Workshop on Philosophical Logic (2015), S. Ju, H. Liu, and H. Ono, Eds., Springer Berlin Heidelberg, pp. 71–85.DOI
  16. [16]Mayer, A., and Stockmeyer, L. The complexity of PDL with interleaving. Theoretical Computer Science 161, 1 (1996), 109–122.
  17. [17]Parikh, R. Propositional game logic. In 24th Annual Symposium on Foundations of Computer Science (SFCS’83) (1983), IEEE Computer Society, pp. 195–200.DOI
  18. [18]Pauly, M., and Parikh, R. Game logic – An overview. Studia Logica 75, 2 (2003), 165–182.DOI
  19. [19]Pratt, V. A near-optimal method for reasoning about action. Journal of Computer and System Sciences 20, 2 (1980), 231–254.DOI
  20. [20]Sedliár, I. Finitely-valued propositional dynamic logic. In Advances in Modal Logic (AiML’20) (2020), N. Olivetti, R. Verbrugge, S. Negri, and G. Sandu, Eds., vol. 13, College Publications, pp. 561–579.
  21. [21]Sedliár, I. Decidability and complexity of some finitely-valued dynamic logics. In 18th International Conference on Principles of Knowledge Representation and Reasoning (KR’21) (2021), pp. 570–580.
  22. [22]van Benthem, J., van Eijck, J., and Kooi, B. Logics of communication and change. Information and Computation 204, 11 (2006), 1620–1662.
  23. [23]van Ditmarsch, H., van der Hoek, W., and Kooi, B. Dynamic Epistemic Logic, vol. 337 of Synthese Library. Springer Dordrecht, 2008.
  24. [24]van Eijck, J., and Wang, Y. Propositional dynamic logic as a logic of belief revision. In Logic, Language, Information and Computation (WoLLIC’08) (2008), W. Hodges and R. de Queiroz, Eds., vol. 5110 of LNCS, Springer Berlin Heidelberg, pp. 136–148.DOI
  25. [25]Warshall, S. A theorem on Boolean matrices. Journal of the ACM 9, 1 (1962), 11–12.DOI

Paper details

vlnc:W_buvm5pka
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents