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 π : X 2 → N ∞ R_{\pi}: X^{2} \to\mathbb{N}_{\infty} R π : X 2 → N ∞ , where the weight R π ( x , y ) R_{\pi}(x,y) R π ( x , y ) is an extended natural number modeling the (least) cost of reaching y y y via executing π \pi π at x x x . In particular, the addition of natural numbers is seen as cost combination and the weights 0 0 0 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 ⟨ π ⟩ ≤ m φ for every (non-extended) natural number m ∈ N m \in\mathbb{N} m ∈ N , intuitively stating that ‘executing π \pi π to reach φ \varphi φ is possible for a cost of no more than m m m ’. 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 φ → [ π ] ∗ m φ can be read as ‘φ \varphi φ is preserved while looping π \pi π without exceeding cost m m m ’. 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 F L ( φ ) FL(\varphi) F L ( φ ) for every formula φ \varphi φ . The size ∣ F L ( φ ) ∣ |FL(\varphi)| ∣ F L ( φ ) ∣ remains finite with upper bound ∥ φ ∥ N ∈ N \|\varphi\|_{\mathbb{N}} \in\mathbb{N} ∥ φ ∥ N ∈ 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 property 1 (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 ∈ N N(\varphi)+1 \in\mathbb{N} N ( φ ) + 1 ∈ 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\} N ∞ := N ∪ { ∞ } , 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 ⟨ N ∞ , ∧ , + , ∞ , 0 ⟩ 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 x + ∞ = ∞ + x = ∞ ). 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 ⟨ X , R ⟩ consists of a set of states X X X together with a weighted accessibility relation R : X 2 → N ∞ R: X^2 \to\mathbb{N}^{\infty} R : X 2 → N ∞ .
The value R ( x , y ) ∈ N ∞ R(x,y) \in\mathbb{N}^{\infty} R ( x , y ) ∈ N ∞ models the (least) cost of the R R R -transition from x x x to y y y . In particular, every Kripke frame R ⊆ X 2 R \subseteq X^2 R ⊆ X 2 can be naturally seen as a cost frame via R ( x , y ) = 0 ⇔ x R y R(x,y) = 0 \Leftrightarrow xRy R ( x , y ) = 0 ⇔ x R y and R ( x , y ) = ∞ ⇔ ¬ x R y R(x,y) = \infty\Leftrightarrow\neg xRy R ( x , y ) = ∞ ⇔ ¬ x R y . That is, cost 0 0 0 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 , R 1 ⟩ \langle X, R_1\rangle ⟨ X , R 1 ⟩ and ⟨ X , R 2 ⟩ \langle X, R_2\rangle ⟨ X , R 2 ⟩ be cost frames. The sequential composition of R 1 R_1 R 1 and R 2 R_2 R 2 is the weighted relation R 1 ∘ R 2 : X 2 → N ∞ R_1 \circ R_2: X^2 \to\mathbb{N}^{\infty} R 1 ∘ R 2 : X 2 → N ∞ defined by
( R 1 ∘ R 2 ) ( x , y ) = ⋀ v ∈ X R 1 ( x , v ) + R 2 ( v , y ) . (R_1 \circ R_2)(x,y) = \bigwedge_{v \in X} R_1(x,v) + R_2(v,y). ( R 1 ∘ R 2 ) ( x , y ) = v ∈ X ⋀ R 1 ( x , v ) + R 2 ( v , y ) .
That is, R 1 ∘ R 2 ( x , y ) R_1 \circ R_2(x,y) R 1 ∘ R 2 ( x , y ) represents the least cost to get from x x x to y y y by an R 1 R_1 R 1 -transition followed by an R 2 R_2 R 2 -transition (where + + + corresponds to cost combination). Similarly, we generalize reflexive transitive closures. For any subset S ⊆ X S \subseteq X S ⊆ X , define the diagonal Δ S : X 2 → N ∞ \Delta_S: X^2 \to\mathbb{N}^{\infty} Δ S : X 2 → N ∞ by
Δ S ( x , y ) = { 0 if 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} Δ S ( x , y ) = { 0 ∞ if x = y & x ∈ S , otherwise.
Definition 2.3 (Iteration). For ⟨ X , R ⟩ \langle X, R\rangle ⟨ X , R ⟩ a cost frame, inductively define R [ k ] : X 2 → N ∞ R^{[k]}: X^2 \to\mathbb{N}^{\infty} R [ k ] : X 2 → N ∞ for all k ≥ 0 k \geq0 k ≥ 0 by R [ 0 ] = Δ X R^{[0]} = \Delta_X R [ 0 ] = Δ X and R [ k + 1 ] = R ∘ R [ k ] R^{[k+1]} = R \circ R^{[k]} R [ k + 1 ] = R ∘ R [ k ] . The iteration R ∗ : X 2 → N ∞ R^*: X^2 \to\mathbb{N}^{\infty} R ∗ : X 2 → N ∞ is defined by
R ∗ ( x , y ) = ⋀ k ≥ 0 R [ k ] ( x , y ) . R^*(x,y) = \bigwedge_{k \geq0} R^{[k]}(x,y). R ∗ ( x , y ) = k ≥ 0 ⋀ R [ k ] ( x , y ) .
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} P ∞ -coalgebras where P ∞ : X ↦ ( N ∞ ) X \mathcal{P}_{\infty}: X \mapsto(\mathbb{N}^{\infty})^X P ∞ : X ↦ ( N ∞ ) X is an appropriate generalization of the covariant powerset functor P \mathcal{P} 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 P N ∞ \mathcal{P}_{\mathbb{N}^{\infty}} P N ∞ ).
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} φ π ::= p ∣ ¬ φ ∣ φ 1 ∧ φ 2 ∣ ⟨ π ⟩ m φ ::= a ∣ π 1 ∪ π 2 ∣ π 1 ; π 2 ∣ π ∗ ∣ ψ ? Here, p ∈ Φ 0 p \in\Phi_0 p ∈ Φ 0 and a ∈ Π 0 a \in\Pi_0 a ∈ Π 0 range over countable collections of propositional variables and atomic programs , respectively, and m ∈ N m \in\mathbb{N} m ∈ 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 [ π ] m φ := ¬ ⟨ π ⟩ m ¬ φ . 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 , { R a } a ∈ Π 0 , V a l ⟩ \mathcal{M} = \langle X, \{R_a\}_{a\in\Pi_0}, \mathrm{Val}\rangle M = ⟨ X , { R a } a ∈ Π 0 , Val ⟩ such that ⟨ X , R a ⟩ \langle X, R_a\rangle ⟨ X , R a ⟩ is a cost frame for every atomic program a ∈ Π 0 a \in\Pi_0 a ∈ Π 0 and V a l : Φ 0 → P ( X ) \mathrm{Val}: \Phi_0 \to\mathcal{P}(X) Val : Φ 0 → P ( X ) is a propositional valuation.
Definition 2.8 (Satisfaction). For a model M = ⟨ X , { R a } a ∈ Π 0 , V a l ⟩ \mathcal{M} = \langle X, \{R_a\}_{a\in\Pi_0}, \mathrm{Val}\rangle M = ⟨ X , { R a } a ∈ Π 0 , Val ⟩ and x ∈ X x \in X x ∈ X , inductively define M , x ⊩ φ \mathcal{M}, x \Vdash\varphi M , x ⊩ φ for all φ ∈ Φ \varphi\in\Phi φ ∈ Φ and R π : X 2 → N ∞ R_\pi: X^2 \to\mathbb{N}^{\infty} R π : X 2 → N ∞ for all π ∈ Π \pi\in\Pi π ∈ Π :
Formulas:
M , x ⊩ p \mathcal{M}, x \Vdash p M , x ⊩ p iff x ∈ V a l ( p ) x \in\mathrm{Val}(p) x ∈ Val ( p )
M , x ⊩ φ ∧ ψ \mathcal{M}, x \Vdash\varphi\wedge\psi M , x ⊩ φ ∧ ψ iff M , x ⊩ φ \mathcal{M}, x \Vdash\varphi M , x ⊩ φ & M , x ⊩ ψ \mathcal{M}, x \Vdash\psi M , x ⊩ ψ
M , x ⊩ ¬ φ \mathcal{M}, x \Vdash\neg\varphi M , x ⊩ ¬ φ iff M , x ⊮ φ \mathcal{M}, x \not\Vdash\varphi M , x ⊩ φ
M , x ⊩ ⟨ π ⟩ m φ \mathcal{M}, x \Vdash\langle\pi\rangle^m\varphi M , x ⊩ ⟨ π ⟩ m φ iff ∃ y : R π ( x , y ) ≤ m \exists y : R_\pi(x,y) \le m ∃ y : R π ( x , y ) ≤ m & M , y ⊩ φ \mathcal{M}, y \Vdash\varphi M , y ⊩ φ
Programs:
R π 1 ∪ π 2 = R π 1 ∧ R π 2 R_{\pi_1\cup\pi_2} = R_{\pi_1} \wedge R_{\pi_2} R π 1 ∪ π 2 = R π 1 ∧ R π 2
R π 1 ; π 2 = R π 1 ∘ R π 2 R_{\pi_1;\pi_2} = R_{\pi_1} \circ R_{\pi_2} R π 1 ; π 2 = R π 1 ∘ R π 2
R π ∗ = ( R π ) ∗ R_{\pi^*} = (R_\pi)^* R π ∗ = ( R π ) ∗
R ψ ? = Δ [ [ ψ ] ] R_{\psi?} = \Delta_{[\![\psi]\!]} R ψ ? = Δ [ [ ψ ] ] ([ [ ψ ] ] = { x ∣ M , x ⊩ ψ } [\![\psi]\!] = \{x \mid\mathcal{M}, x \Vdash\psi\} [ [ ψ ] ] = { x ∣ M , x ⊩ ψ } )
(R 1 ∧ R 2 R_1 \wedge R_2 R 1 ∧ R 2 is the point-wise minimum. For ∘ \circ ∘ , Δ \Delta Δ , and R ∗ R^* R ∗ recall Definitions 2.2 & 2.3 .)
As usual, we say that φ \varphi φ is satisfiable if M , x ⊩ φ \mathcal{M}, x \Vdash\varphi M , x ⊩ φ holds at some state of some model and valid if M , x ⊩ φ \mathcal{M}, x \Vdash\varphi M , x ⊩ φ holds at all states of all models.
By definition, the clause for the dual modalities is M , x ⊩ [ π ] m φ \mathcal{M}, x \Vdash[\pi]^m\varphi M , x ⊩ [ π ] m φ iff ∀ y : R π ( x , y ) ≤ m ⇒ M , y ⊩ φ \forall y: R_\pi(x,y) \le m \Rightarrow\mathcal{M}, y \Vdash\varphi ∀ y : R π ( x , y ) ≤ m ⇒ M , y ⊩ φ . The formula ⟨ π ⟩ m φ \langle\pi\rangle^m\varphi ⟨ π ⟩ m φ intuitively states that ‘executing π \pi π to reach a state where φ \varphi φ holds is possible for a cost of no more than m m m ’ and [ π ] m φ [\pi]^m\varphi [ π ] m φ expresses that ‘every execution of π \pi π on a resource-budget at most m m m results in property φ \varphi φ ’. With this, further cost-sensitive properties about programs can be expressed, for instance ⟨ π ⟩ m ⊤ \langle\pi\rangle^m\top ⟨ π ⟩ m ⊤ can be read as ‘program π \pi π terminates without costing more than m m m ’ and φ → [ π ∗ ] m φ \varphi\to[\pi^*]^m\varphi φ → [ π ∗ ] m φ can be read as ‘φ \varphi φ is preserved when looping π \pi π as long as cost m m m is not exceeded ’.
As mentioned before, the weights on the accessibility relation R π R_\pi R π correspond to the *(least) costs of executing program π \pi π . This interpretation also pertains to more complex programs, for instance the program if φ \varphi φ then π 1 \pi_1 π 1 else π 2 : = φ ? ; π 1 ∪ ¬ φ ? ; π 2 \pi_2 := \varphi?;\pi_1 \cup\neg\varphi?;\pi_2 π 2 := φ ? ; π 1 ∪ ¬ φ ? ; π 2 corresponds to
R i f φ t h e n π 1 e l s e π 2 ( x , y ) = { R π 1 ( x , y ) if M , x ⊩ φ , R π 2 ( x , y ) otherwise. R_{\mathrm{if}\ \varphi\ \mathrm{then}\ \pi_1\ \mathrm{else}\ \pi_2}(x,y) =
\begin{cases}
R_{\pi_1}(x,y) & \text{if } \mathcal{M},x \Vdash\varphi,\\
R_{\pi_2}(x,y) & \text{otherwise.}
\end{cases} R if φ then π 1 else π 2 ( x , y ) = { R π 1 ( x , y ) R π 2 ( x , y ) if M , x ⊩ φ , otherwise.
Note that we implicitly assume (by definition of Δ \Delta Δ ) that testing itself does not have a cost. However, such costs can also be accommodated, e.g. using ‘indexed tests’ R ψ ? n = Δ [ [ ψ ] ] ∨ n R_{\psi?n}=\Delta[[\psi]]\lor n R ψ ? n = Δ [[ ψ ]] ∨ n .
In the following two examples, we consider some sample applications of NPDL.
Example 2.9 (Resource-bounded verification of a countdown loop). Consider a simple program that repeatedly decrements a non-negative integer counter until it reaches zero. We use a cost model in which each decrement operation has cost 1, while evaluating a test has cost 0. This allows us to interpret the cost of an execution as the number of decrement operations performed.
We model the program configurations by the set of states X = N X=\mathbb{N} X = N , where each state n n n represents a configuration in which the counter has value n n n . Let positive and zero be propositional variables with valuations
Val ( p o s i t i v e ) = N ∖ { 0 } , Val ( z e r o ) = { 0 } . \operatorname{Val}(\mathit{positive})=\mathbb{N}\setminus\{0\},\qquad\operatorname{Val}(\mathit{zero})=\{0\}. Val ( positive ) = N ∖ { 0 } , Val ( zero ) = { 0 } . Furthermore, let dec be an atomic program representing the decrement operation. Its cost relation is defined by
R d e c ( n , m ) = { 1 if n > 0 and m = n − 1 , ∞ otherwise. R_{\mathit{dec}}(n,m)=
\begin{cases}
1 & \text{if } n>0 \text{ and } m=n-1,\\
\infty& \text{otherwise.}
\end{cases} R dec ( n , m ) = { 1 ∞ if n > 0 and m = n − 1 , otherwise. Thus, decrementing a positive counter incurs cost 1, whereas no decrement transition is available from the state 0. The body of the loop and the entire loop can now be represented by the program
π d e c ≔ ( p o s i t i v e ? ; d e c ) ∗ . \pi_{\mathit{dec}}\coloneqq(\mathit{positive}?;\mathit{dec})^{*}. π dec : = ( positive ? ; dec ) ∗ . The test ensures that the counter is positive before each decrement. Consequently, every iteration of δ \delta δ is executable at cost 1, and the loop terminates when the counter reaches zero.
Let us first consider the cost relation induced by the loop. Starting in state n n n , executing exactly k k k iterations, where 0 ≤ k ≤ n 0\leq k\leq n 0 ≤ k ≤ n , reaches state n − k n-k n − k at cost k k k . No execution can perform more than n n n iterations. It follows that
R π d e c ( n , m ) = { n − m if 0 ≤ m ≤ n , ∞ otherwise. R_{\pi_{\mathit{dec}}}(n,m)=
\begin{cases}
n-m & \text{if } 0\leq m\leq n,\\
\infty& \text{otherwise.}
\end{cases} R π dec ( n , m ) = { n − m ∞ if 0 ≤ m ≤ n , otherwise. In particular, the least cost of reaching the zero state is R π d e c ( n , 0 ) = n R_{\pi_{\mathit{dec}}}(n,0)=n R π dec ( n , 0 ) = n . This observation can be expressed directly in NPDL. For every initial counter value n ∈ N n\in\mathbb{N} n ∈ N and every cost bound B ∈ N B\in\mathbb{N} B ∈ N , we have
M , n ⊩ ⟨ π d e c ⟩ B z e r o ⟺ n ≤ B . \mathcal{M},n\Vdash\langle\pi_{\mathit{dec}}\rangle^{B}\mathit{zero}\quad\Longleftrightarrow\quad n\leq B. M , n ⊩ ⟨ π dec ⟩ B zero ⟺ n ≤ B . Hence, the formula ⟨ π d e c ⟩ B z e r o \langle\pi_{\mathit{dec}}\rangle^{B}\mathit{zero} ⟨ π dec ⟩ B zero expresses that the countdown loop can reach a configuration in which the counter is zero within the available cost budget B B B . In this example, the formula holds precisely when the budget is sufficient to complete the loop.
For instance, if the initial counter value is 3, the execution is
3 → 1 2 → 1 1 → 1 0 , 3\xrightarrow{1}2\xrightarrow{1}1\xrightarrow{1}0, 3 1 2 1 1 1 0 , where each transition is labelled by its cost. The formula ⟨ π d e c ⟩ 2 z e r o \langle\pi_{\mathit{dec}}\rangle^{2}\mathit{zero} ⟨ π dec ⟩ 2 zero is false at state 3, whereas ⟨ π d e c ⟩ 3 z e r o \langle\pi_{\mathit{dec}}\rangle^{3}\mathit{zero} ⟨ π dec ⟩ 3 zero is true there. The former budget is insufficient to reach the zero state, while the latter is sufficient.
The example also illustrates the role of the dual modality. Suppose that safe is a propositional variable describing the configurations that satisfy a given safety requirement. Then [ π d e c ] B s a f e [\pi_{\mathit{dec}}]^{B}\mathit{safe} [ π dec ] B safe expresses that every state reachable from the initial configuration with least execution cost at most B B B satisfies the safety requirement.
Since the program uses iteration, this includes states reached after any number of loop iterations, including the initial state itself.
Finally, the cost assignment can be modified to model other resource measures. For example, if every decrement operation has cost c > 0 c > 0 c > 0 instead of cost 1, the least cost of reaching zero from state n n n becomes c n cn c n , and the termination formula holds precisely when c n ≤ B cn \le B c n ≤ B . More generally, assigning different costs to different decrement operations allows the logic to express termination requirements under non-uniform resource consumption.
Example 2.10 (Budgeted network routing). Consider a communication network whose nodes are states of a model M \mathcal{M} M . Let forward be an atomic program representing the forwarding of a packet between adjacent nodes, where the cost R f o r w a r d ( x , y ) R_{\mathrm{forward}}(x,y) R forward ( x , y ) represents the latency or energy required to forward a packet from x x x to y y y . A cost of ∞ \infty ∞ indicates that no direct transition is available.
Suppose the network contains four nodes s , u , v , t s,u,v,t s , u , v , t and the following transitions:
Table 2.10.
All other transitions have cost ∞ \infty ∞ . Let delivered be a propositional variable that holds precisely at the destination node t t t .
There are two routes from s s s to t t t : the route through u u u has total cost 1 + 4 = 5 1 + 4 = 5 1 + 4 = 5 , whereas the route through v v v has total cost 2 + 1 = 3 2 + 1 = 3 2 + 1 = 3 . Consequently,
R f o r w a r d ∗ ( s , t ) = min { 1 + 4 , 2 + 1 } = 3. R_{\mathrm{forward}^{*}}(s,t) = \min\{1+4,2+1\}=3. R forward ∗ ( s , t ) = min { 1 + 4 , 2 + 1 } = 3.
The formula
⟨ f o r w a r d ∗ ⟩ B d e l i v e r e d \langle\mathrm{forward}^{*}\rangle^{B}\mathrm{delivered} ⟨ forward ∗ ⟩ B delivered
therefore holds at s s s if and only if B ≥ 3 B \ge3 B ≥ 3 . In particular, ⟨ f o r w a r d ∗ ⟩ 2 d e l i v e r e d \langle\mathrm{forward}^{*}\rangle^{2}\mathrm{delivered} ⟨ forward ∗ ⟩ 2 delivered is false at s s s , whereas ⟨ f o r w a r d ∗ ⟩ 3 d e l i v e r e d \langle\mathrm{forward}^{*}\rangle^{3}\mathrm{delivered} ⟨ forward ∗ ⟩ 3 delivered is true.
Thus, NPDL can express whether a destination is reachable within a prescribed resource budget, while the semantics of sequential composition and iteration computes the least cost over all possible routes. Depending on the interpretation of transition costs, the same model can represent latency-constrained routing, energy-aware communication, or other budget-constrained reachability problems.
We end this section with some validities of NPDL. Note that (4) & (7) for choice and test below are the same as in PDL, while (5) & (6) for composition and iteration are more involved.
Proposition 2.11. The following are valid NPDL-formulas.
⟨ π ⟩ m ⊥ ↔ ⊥ \langle\pi\rangle^{m}\bot\leftrightarrow\bot ⟨ π ⟩ m ⊥ ↔ ⊥
⟨ π ⟩ m ( φ ∨ ψ ) ↔ ⟨ π ⟩ m φ ∨ ⟨ π ⟩ m ψ \langle\pi\rangle^{m}(\varphi\lor\psi) \leftrightarrow\langle\pi\rangle^{m}\varphi\lor\langle\pi\rangle^{m}\psi ⟨ π ⟩ m ( φ ∨ ψ ) ↔ ⟨ π ⟩ m φ ∨ ⟨ π ⟩ m ψ
⟨ π ⟩ n φ → ⟨ π ⟩ m φ \langle\pi\rangle^{n}\varphi\to\langle\pi\rangle^{m}\varphi ⟨ π ⟩ n φ → ⟨ π ⟩ m φ for all n ≤ m n \le m n ≤ m
⟨ π 1 ∪ π 1 ⟩ m φ ↔ ⟨ π 1 ⟩ m φ ∨ ⟨ π 2 ⟩ m φ \langle\pi_{1}\cup\pi_{1}\rangle^{m}\varphi\leftrightarrow\langle\pi_{1}\rangle^{m}\varphi\lor\langle\pi_{2}\rangle^{m}\varphi ⟨ π 1 ∪ π 1 ⟩ m φ ↔ ⟨ π 1 ⟩ m φ ∨ ⟨ π 2 ⟩ m φ
⟨ π 1 ; π 2 ⟩ m φ ↔ ⋁ i = 0 m ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ \langle\pi_{1};\pi_{2}\rangle^{m}\varphi\leftrightarrow\bigvee_{i=0}^{m}\langle\pi_{1}\rangle^{m-i}\langle\pi_{2}\rangle^{i}\varphi ⟨ π 1 ; π 2 ⟩ m φ ↔ ⋁ i = 0 m ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ
⟨ π ∗ ⟩ m φ ↔ φ ∨ ⋁ i = 0 m ⟨ π ⟩ m − i ⟨ π ∗ ⟩ i φ \langle\pi^{*}\rangle^{m}\varphi\leftrightarrow\varphi\lor\bigvee_{i=0}^{m}\langle\pi\rangle^{m-i}\langle\pi^{*}\rangle^{i}\varphi ⟨ π ∗ ⟩ m φ ↔ φ ∨ ⋁ i = 0 m ⟨ π ⟩ m − i ⟨ π ∗ ⟩ i φ
⟨ ψ ? ⟩ m φ ↔ ψ ∧ φ \langle\psi?\rangle^{m}\varphi\leftrightarrow\psi\land\varphi ⟨ ψ ? ⟩ m φ ↔ ψ ∧ φ
Proof. Let M = ⟨ X , { R a } a ∈ Π 0 , V a l ⟩ \mathcal{M}=\langle X,\{R_a\}_{a\in\Pi_0},\mathrm{Val}\rangle M = ⟨ X , { R a } a ∈ Π 0 , Val ⟩ be a model. The proofs of (1)–(3) are completely straightforward using the satisfiability clause for M , x ⊨ ⟨ π ⟩ m φ \mathcal{M},x \models\langle\pi\rangle^{m}\varphi M , x ⊨ ⟨ π ⟩ m φ of Definition 2.8. (4): Follows from R π 1 ( x , y ) ∧ R π 2 ( x , y ) ≤ m R_{\pi_1}(x,y) \land R_{\pi_2}(x,y) \le m R π 1 ( x , y ) ∧ R π 2 ( x , y ) ≤ m if and only if R π 1 ( x , y ) ≤ m R_{\pi_1}(x,y) \le m R π 1 ( x , y ) ≤ m or R π 2 ( x , y ) ≤ m R_{\pi_2}(x,y) \le m R π 2 ( x , y ) ≤ m .
(5): M , x ⊩ ⟨ π 1 ; π 2 ⟩ m φ \mathcal{M},x \Vdash\langle\pi_1;\pi_2\rangle^m\varphi M , x ⊩ ⟨ π 1 ; π 2 ⟩ m φ iff there exist v , y ∈ X v,y \in X v , y ∈ X such that R π 1 ( x , v ) + R π 2 ( v , y ) ≤ m R_{\pi_1}(x,v)+R_{\pi_2}(v,y) \le m R π 1 ( x , v ) + R π 2 ( v , y ) ≤ m and M , y ⊩ φ \mathcal{M},y \Vdash\varphi M , y ⊩ φ . The equivalence to the right-hand side of the formula is clear with i : = R π 2 ( v , y ) i := R_{\pi_2}(v,y) i := R π 2 ( v , y ) .
(6): M , x ⊩ ⟨ π ∗ ⟩ m φ \mathcal{M},x \Vdash\langle\pi^*\rangle^m\varphi M , x ⊩ ⟨ π ∗ ⟩ m φ iff there is y ∈ X y \in X y ∈ X and k ≥ 0 k \ge0 k ≥ 0 such that ( R π ) [ k ] ( x , y ) ≤ m (R_\pi)^{[k]}(x,y) \le m ( R π ) [ k ] ( x , y ) ≤ m and M , y ⊩ φ \mathcal{M},y \Vdash\varphi M , y ⊩ φ . The case of ( R π ) [ 0 ] ( x , y ) ≤ m (R_\pi)^{[0]}(x,y) \le m ( R π ) [ 0 ] ( x , y ) ≤ m is equivalent to x = y x=y x = y and M , x ⊩ φ \mathcal{M},x \Vdash\varphi M , x ⊩ φ . The case of ( R π ) [ k + 1 ] ( x , y ) (R_\pi)^{[k+1]}(x,y) ( R π ) [ k + 1 ] ( x , y ) with k ≥ 0 k \ge0 k ≥ 0 holds if and only if there is v ∈ X v \in X v ∈ X such that R π ( x , v ) + ( R π ) [ k ] ( v , y ) ≤ m R_\pi(x,v)+(R_\pi)^{[k]}(v,y) \le m R π ( x , v ) + ( R π ) [ k ] ( v , y ) ≤ m . Setting i : = ( R π ) [ k ] ( v , y ) i := (R_\pi)^{[k]}(v,y) i := ( R π ) [ k ] ( v , y ) this is equivalent to M , x ⊩ ⟨ π ⟩ m − i ⟨ π ∗ ⟩ i φ \mathcal{M},x \Vdash\langle\pi\rangle^{m-i}\langle\pi^*\rangle^i\varphi M , x ⊩ ⟨ π ⟩ m − i ⟨ π ∗ ⟩ i φ .
(7): M , x ⊩ ⟨ ψ ? ⟩ m φ \mathcal{M},x \Vdash\langle\psi?\rangle^m\varphi M , x ⊩ ⟨ ψ ? ⟩ m φ iff there is y ∈ X y \in X y ∈ X with R ψ ? ( x , y ) ≤ m R_{\psi?}(x,y) \le m R ψ ? ( x , y ) ≤ m and M , y ⊩ φ \mathcal{M},y \Vdash\varphi M , y ⊩ φ , and the former is equivalent to x = y x=y x = y and M , x ⊩ ψ \mathcal{M},x \Vdash\psi M , x ⊩ ψ . □
These validities motivate our definition of Fischer-Ladner closure (Definition 3.1) and are used in the proof of the corresponding Filtration Theorem (Theorem 3.7) in the next section.
Decidability
In this section, we prove that NPDL is decidable, which we do in two steps. First, we show the bounded finite model property using filtrations through the Fischer-Ladner closure adequately defined for our framework (Subsections 3.1 & 3.2). Second, we show that there is a bound on weights of atomic programs sufficient to check satisfiability of a formula (Subsection 3.3).
The Fischer-Ladner Closure
We aim to prove the bounded finite model property using filtrations through an appropriately defined Fischer-Ladner closure [6 Theorem 3.2] , a finite set of formulas closed under reduction instances for program constructs. Our presentation here is similar to [10 Section 6] .
Definition 3.1 (Fischer-Ladner closure). For all formulas φ \varphi φ and programs π \pi π we define the sets of formulas F L ( φ ) FL(\varphi) F L ( φ ) and F L ⋄ ( ⟨ π ⟩ m φ ) FL^\diamond(\langle\pi\rangle^m\varphi) F L ⋄ (⟨ π ⟩ m φ ) for all m ∈ N m \in\mathbb{N} m ∈ N as follows.
Formulas:
F L ( p ) = { p } FL(p)=\{p\} F L ( p ) = { p } for propositional variables p ∈ Φ 0 p \in\Phi_0 p ∈ Φ 0 ,
F L ( ¬ φ ) = { ¬ φ } ∪ F L ( φ ) FL(\neg\varphi)=\{\neg\varphi\}\cup FL(\varphi) F L ( ¬ φ ) = { ¬ φ } ∪ F L ( φ ) ,
F L ( φ 1 ∧ φ 2 ) = { φ 1 ∧ φ 2 } ∪ F L ( φ 1 ) ∪ F L ( φ 2 ) FL(\varphi_1\land\varphi_2)=\{\varphi_1\land\varphi_2\}\cup FL(\varphi_1)\cup FL(\varphi_2) F L ( φ 1 ∧ φ 2 ) = { φ 1 ∧ φ 2 } ∪ F L ( φ 1 ) ∪ F L ( φ 2 ) ,
F L ( ⟨ π ⟩ m φ ) = F L ⋄ ( ⟨ π ⟩ m φ ) ∪ F L ( φ ) FL(\langle\pi\rangle^m\varphi)=FL^\diamond(\langle\pi\rangle^m\varphi)\cup FL(\varphi) F L (⟨ π ⟩ m φ ) = F L ⋄ (⟨ π ⟩ m φ ) ∪ F L ( φ ) ,
Programs:
F L ⋄ ( ⟨ a ⟩ m φ ) = { ⟨ a ⟩ m φ } FL^\diamond(\langle a\rangle^m\varphi)=\{\langle a\rangle^m\varphi\} F L ⋄ (⟨ a ⟩ m φ ) = {⟨ a ⟩ m φ } for atomic programs a ∈ Π 0 a \in\Pi_0 a ∈ Π 0 ,
F L ⋄ ( ⟨ π 1 ∪ π 2 ⟩ m φ ) = { ⟨ π 1 ∪ π 2 ⟩ m φ } ∪ F L ⋄ ( ⟨ π 1 ⟩ m φ ) ∪ F L ⋄ ( ⟨ π 2 ⟩ m φ ) FL^\diamond(\langle\pi_1\cup\pi_2\rangle^m\varphi)=\{\langle\pi_1\cup\pi_2\rangle^m\varphi\}\cup FL^\diamond(\langle\pi_1\rangle^m\varphi)\cup FL^\diamond(\langle\pi_2\rangle^m\varphi) F L ⋄ (⟨ π 1 ∪ π 2 ⟩ m φ ) = {⟨ π 1 ∪ π 2 ⟩ m φ } ∪ F L ⋄ (⟨ π 1 ⟩ m φ ) ∪ F L ⋄ (⟨ π 2 ⟩ m φ ) ,
F L ⋄ ( ⟨ π 1 ; π 2 ⟩ m φ ) = { ⟨ π 1 ; π 2 ⟩ m φ } ∪ ⋃ i = 0 m F L ⋄ ( ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ ) ∪ F L ⋄ ( ⟨ π 2 ⟩ m φ ) FL^\diamond(\langle\pi_1;\pi_2\rangle^m\varphi)=\{\langle\pi_1;\pi_2\rangle^m\varphi\}\cup\bigcup_{i=0}^{m}FL^\diamond(\langle\pi_1\rangle^{m-i}\langle\pi_2\rangle^i\varphi)\cup FL^\diamond(\langle\pi_2\rangle^m\varphi) F L ⋄ (⟨ π 1 ; π 2 ⟩ m φ ) = {⟨ π 1 ; π 2 ⟩ m φ } ∪ ⋃ i = 0 m F L ⋄ (⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ ) ∪ F L ⋄ (⟨ π 2 ⟩ m φ ) ,
F L ⋄ ( ⟨ π ∗ ⟩ m φ ) = ⋃ n + n ′ ≤ m F L ⋄ ( ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) ∪ { ⟨ π ∗ ⟩ m φ } FL^\diamond(\langle\pi^*\rangle^m\varphi)=\bigcup_{n+n'\le m}FL^\diamond(\langle\pi\rangle^n\langle\pi^*\rangle^{n'}\varphi)\cup\{\langle\pi^*\rangle^m\varphi\} F L ⋄ (⟨ π ∗ ⟩ m φ ) = ⋃ n + n ′ ≤ m F L ⋄ (⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) ∪ {⟨ π ∗ ⟩ m φ } ,
F L ⋄ ( ⟨ ψ ? ⟩ m φ ) = { ⟨ ψ ? ⟩ m φ } ∪ F L ( ψ ) FL^\diamond(\langle\psi?\rangle^m\varphi)=\{\langle\psi?\rangle^m\varphi\}\cup FL(\psi) F L ⋄ (⟨ ψ ? ⟩ m φ ) = {⟨ ψ ? ⟩ m φ } ∪ F L ( ψ ) .
We refer to the collection of formulas F L ( φ ) FL(\varphi) F L ( φ ) as the Fischer-Ladner closure of φ \varphi φ .
Our first goal is to show that F L ( φ ) FL(\varphi) F L ( φ ) is always finite with an upper bound ∥ φ ∥ N \|\varphi\|_{\mathbb{N}} ∥ φ ∥ N parametric in φ \varphi φ . Note that, due to the closure conditions for sequential composition and iteration above, this upper bound can not simply be the length of φ \varphi φ (as is the case in standard PDL).
Definition 3.2. For all formulas φ \varphi φ and programs π \pi π we define the natural numbers ∥ φ ∥ N \|\varphi\|_{\mathbb{N}} ∥ φ ∥ N and ∥ ⟨ π ⟩ m ∥ N \|\langle\pi\rangle^m\|_{\mathbb{N}} ∥ ⟨ π ⟩ m ∥ N for every m ∈ N m \in\mathbb{N} m ∈ N as follows.
Formulas:
∥ p ∥ N = 1 \lVert p\rVert_{\mathbb{N}} = 1 ∥ p ∥ N = 1 for propositional variables,
∥ ¬ φ ∥ N = 1 + ∥ φ ∥ N \lVert\neg\varphi\rVert_{\mathbb{N}} = 1 + \lVert\varphi\rVert_{\mathbb{N}} ∥ ¬ φ ∥ N = 1 + ∥ φ ∥ N ,
∥ φ 1 ∧ φ 2 ∥ N = 1 + ∥ φ 1 ∥ N + ∥ φ 2 ∥ N \lVert\varphi_{1}\land\varphi_{2}\rVert_{\mathbb{N}} = 1 + \lVert\varphi_{1}\rVert_{\mathbb{N}} + \lVert\varphi_{2}\rVert_{\mathbb{N}} ∥ φ 1 ∧ φ 2 ∥ N = 1 + ∥ φ 1 ∥ N + ∥ φ 2 ∥ N ,
∥ ⟨ π ⟩ m φ ∥ N = ∥ ⟨ π ⟩ m ∥ N + ∥ φ ∥ N \lVert\langle\pi\rangle^{m}\varphi\rVert_{\mathbb{N}} = \lVert\langle\pi\rangle^{m}\rVert_{\mathbb{N}} + \lVert\varphi\rVert_{\mathbb{N}} ∥⟨ π ⟩ m φ ∥ N = ∥⟨ π ⟩ m ∥ N + ∥ φ ∥ N .
Programs:
∥ ⟨ a ⟩ m ∥ N = 1 \lVert\langle a\rangle^{m}\rVert_{\mathbb{N}} = 1 ∥⟨ a ⟩ m ∥ N = 1 for atomic programs,
∥ ⟨ π 1 ∪ π 2 ⟩ m ∥ N = 1 + ∥ ⟨ π 1 ⟩ m ∥ N + ∥ ⟨ π 2 ⟩ m ∥ N \lVert\langle\pi_{1}\cup\pi_{2}\rangle^{m}\rVert_{\mathbb{N}} = 1 + \lVert\langle\pi_{1}\rangle^{m}\rVert_{\mathbb{N}} + \lVert\langle\pi_{2}\rangle^{m}\rVert_{\mathbb{N}} ∥⟨ π 1 ∪ π 2 ⟩ m ∥ N = 1 + ∥⟨ π 1 ⟩ m ∥ N + ∥⟨ π 2 ⟩ m ∥ N ,
∥ ⟨ π 1 ; π 2 ⟩ m ∥ N = 1 + ∑ i = 0 m ∥ ⟨ π 1 ⟩ m − i ∥ N + ∥ ⟨ π 2 ⟩ i ∥ N \lVert\langle\pi_{1};\pi_{2}\rangle^{m}\rVert_{\mathbb{N}} = 1 + \sum_{i=0}^{m}\lVert\langle\pi_{1}\rangle^{m-i}\rVert_{\mathbb{N}} + \lVert\langle\pi_{2}\rangle^{i}\rVert_{\mathbb{N}} ∥⟨ π 1 ; π 2 ⟩ m ∥ N = 1 + ∑ i = 0 m ∥⟨ π 1 ⟩ m − i ∥ N + ∥⟨ π 2 ⟩ i ∥ N ,
∥ ⟨ π ∗ ⟩ m ∥ N = ( m + 1 ) + ∑ n + n ′ ≤ m ∥ ⟨ π ⟩ n ∥ N \lVert\langle\pi^{*}\rangle^{m}\rVert_{\mathbb{N}} = (m+1) + \sum_{n+n'\leq m}\lVert\langle\pi\rangle^{n}\rVert_{\mathbb{N}} ∥⟨ π ∗ ⟩ m ∥ N = ( m + 1 ) + ∑ n + n ′ ≤ m ∥⟨ π ⟩ n ∥ N ,
∥ ⟨ ψ ? ⟩ m ∥ N = 1 + ∥ ψ ∥ N \lVert\langle\psi?\rangle^{m}\rVert_{\mathbb{N}} = 1 + \lVert\psi\rVert_{\mathbb{N}} ∥⟨ ψ ? ⟩ m ∥ N = 1 + ∥ ψ ∥ N .
(Since only finite sums are involved, all of these are well-defined natural numbers.)
Lemma 3.3. For all formulas φ \varphi φ it holds that ∣ F L ( φ ) ∣ ≤ ∥ φ ∥ N \lvert FL(\varphi)\rvert\leq\lVert\varphi\rVert_{\mathbb{N}} ∣ F L ( φ )∣ ≤ ∥ φ ∥ N .
Proof. By simultaneous induction show for all formulas φ \varphi φ and programs π \pi π that
∣ F L ( φ ) ∣ ≤ ∥ φ ∥ N and ∣ F L ⋄ ( ⟨ π ⟩ m φ ) ∣ ≤ ∥ ⟨ π ⟩ m ∥ N . \lvert FL(\varphi)\rvert\leq\lVert\varphi\rVert_{\mathbb{N}} \quad\text{and}\quad\lvert FL^{\diamond}(\langle\pi\rangle^{m}\varphi)\rvert\leq\lVert\langle\pi\rangle^{m}\rVert_{\mathbb{N}}. ∣ F L ( φ )∣ ≤ ∥ φ ∥ N and ∣ F L ⋄ (⟨ π ⟩ m φ )∣ ≤ ∥⟨ π ⟩ m ∥ N .
The formula induction is straightforward using the inductive definition of F L ( φ ) FL(\varphi) F L ( φ ) in Definition 3.1 and the corresponding inductive hypotheses. For sequential composition, we compute
∣ F L ⋄ ( ⟨ π 1 ; π 2 ⟩ m φ ) ∣ ≤ 1 + ∑ i = 0 m ∣ F L ⋄ ( ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ ) ∣ + ∣ F L ⋄ ( ⟨ π 2 ⟩ i φ ) ∣ \lvert FL^{\diamond}(\langle\pi_{1};\pi_{2}\rangle^{m}\varphi)\rvert\leq1 + \sum_{i=0}^{m}\lvert FL^{\diamond}(\langle\pi_{1}\rangle^{m-i}\langle\pi_{2}\rangle^{i}\varphi)\rvert+ \lvert FL^{\diamond}(\langle\pi_{2}\rangle^{i}\varphi)\rvert ∣ F L ⋄ (⟨ π 1 ; π 2 ⟩ m φ )∣ ≤ 1 + i = 0 ∑ m ∣ F L ⋄ (⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ )∣ + ∣ F L ⋄ (⟨ π 2 ⟩ i φ )∣
≤ 1 + ∑ i = 0 m ∥ ⟨ π 1 ⟩ m − i ∥ N + ∥ ⟨ π 2 ⟩ i ∥ N = ∥ ⟨ π 1 ; π 2 ⟩ m ∥ N \leq1 + \sum_{i=0}^{m}\lVert\langle\pi_{1}\rangle^{m-i}\rVert_{\mathbb{N}} + \lVert\langle\pi_{2}\rangle^{i}\rVert_{\mathbb{N}} = \lVert\langle\pi_{1};\pi_{2}\rangle^{m}\rVert_{\mathbb{N}} ≤ 1 + i = 0 ∑ m ∥⟨ π 1 ⟩ m − i ∥ N + ∥⟨ π 2 ⟩ i ∥ N = ∥⟨ π 1 ; π 2 ⟩ m ∥ N
where the second inequality uses the inductive hypotheses on π 1 \pi_{1} π 1 and π 2 \pi_{2} π 2 .
For iteration, first we note that as a direct consequence of Definition 3.1, it holds that F L ⋄ ( ⟨ π ∗ ⟩ m φ ) ⊆ { ⟨ π ∗ ⟩ i φ ∣ 0 ≤ i ≤ m } ∪ ⋃ { F L ⋄ ( ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) ∣ n + n ′ ≤ m } FL^{\diamond}(\langle\pi^{*}\rangle^{m}\varphi) \subseteq\{\langle\pi^{*}\rangle^{i}\varphi\mid0 \leq i \leq m\} \cup\bigcup\{FL^{\diamond}(\langle\pi\rangle^{n}\langle\pi^{*}\rangle^{n'}\varphi) \mid n+n' \leq m\} F L ⋄ (⟨ π ∗ ⟩ m φ ) ⊆ {⟨ π ∗ ⟩ i φ ∣ 0 ≤ i ≤ m } ∪ ⋃ { F L ⋄ (⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) ∣ n + n ′ ≤ m } , and therefore
∣ F L ⋄ ( ⟨ π ∗ ⟩ m φ ) ∣ ≤ ∣ { ⟨ π ∗ ⟩ i φ ∣ 0 ≤ i ≤ m } ∣ + ∑ n + n ′ ≤ m ∣ F L ⋄ ( ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) ∣ ≤ ( m + 1 ) + ∑ n + n ′ ≤ m ∥ ⟨ π ⟩ n ∥ N = ∥ ⟨ π ∗ ⟩ m ∥ N \begin{aligned}
\lvert FL^{\diamond}(\langle\pi^{*}\rangle^{m}\varphi)\rvert\leq\lvert\{\langle\pi^{*}\rangle^{i}\varphi\mid0 \leq i \leq m\}\rvert+ \sum_{n+n'\leq m}\lvert FL^{\diamond}(\langle\pi\rangle^{n}\langle\pi^{*}\rangle^{n'}\varphi)\rvert\\
&\leq(m+1) + \sum_{n+n'\leq m}\lVert\langle\pi\rangle^{n}\rVert_{\mathbb{N}} = \lVert\langle\pi^{*}\rangle^{m}\rVert_{\mathbb{N}}
\end{aligned} ∣ F L ⋄ (⟨ π ∗ ⟩ m φ )∣ ≤ ∣{⟨ π ∗ ⟩ i φ ∣ 0 ≤ i ≤ m }∣ + n + n ′ ≤ m ∑ ∣ F L ⋄ (⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ )∣ ≤ ( m + 1 ) + n + n ′ ≤ m ∑ ∥⟨ π ⟩ n ∥ N = ∥⟨ π ∗ ⟩ m ∥ N
as desired, where the second inequality uses the inductive hypothesis on π \pi π . □ \square □
To prove the Filtration Theorem (Theorem 3.7), we use various closure properties of F L ( φ ) FL(\varphi) F L ( φ ) (Corollary 3.5), all of which follow from the next lemma (similar to [10 Lemma 6.1] ).
Lemma 3.4. For all formulas φ \varphi φ and programs π \pi π the following hold.
(i) If ψ ∈ F L ( φ ) \psi\in FL(\varphi) ψ ∈ F L ( φ ) then F L ( ψ ) ⊆ F L ( φ ) FL(\psi) \subseteq FL(\varphi) F L ( ψ ) ⊆ F L ( φ ) ,
(ii) If ψ ∈ F L ⋄ ( ⟨ π ⟩ m φ ) \psi\in FL^{\diamond}(\langle\pi\rangle^{m}\varphi) ψ ∈ F L ⋄ (⟨ π ⟩ m φ ) then F L ( ψ ) ⊆ F L ( ⟨ π ⟩ m φ ) FL(\psi) \subseteq FL(\langle\pi\rangle^{m}\varphi) F L ( ψ ) ⊆ F L (⟨ π ⟩ m φ ) .
Proof. By simultaneous induction we show (i) for all formulas φ \varphi φ and (ii) for all programs π \pi π .
Formula induction. The case p ∈ Φ 0 p \in\Phi_{0} p ∈ Φ 0 is due to F L ( p ) = { p } FL(p) = \{p\} F L ( p ) = { p } and the cases ¬ φ \neg\varphi ¬ φ and φ 1 ∧ φ 2 \varphi_{1}\land\varphi_{2} φ 1 ∧ φ 2 are clear by inductive hypotheses and definitions of F L ( ¬ φ ) FL(\neg\varphi) F L ( ¬ φ ) and F L ( φ 1 ∧ φ 2 ) FL(\varphi_{1}\land\varphi_{2}) F L ( φ 1 ∧ φ 2 ) .
**Case ⟨ π ⟩ m φ : ∗ ∗ I f \langle\pi\rangle^{m}\varphi:** If ⟨ π ⟩ m φ : ∗ ∗ I f \psi \in FL(\langle\pi\rangle^{m}\varphi)$, then by definition ψ ∈ F L ( φ ) \psi\in FL(\varphi) ψ ∈ F L ( φ ) or ψ ∈ F L ⋄ ( ⟨ π ⟩ m φ ) \psi\in FL^{\diamond}(\langle\pi\rangle^{m}\varphi) ψ ∈ F L ⋄ (⟨ π ⟩ m φ ) . In the former case use the inductive hypothesis (i) to find F L ( ψ ) ⊆ F L ( φ ) ⊆ F L ( ⟨ π ⟩ m φ ) FL(\psi) \subseteq FL(\varphi) \subseteq FL(\langle\pi\rangle^{m}\varphi) F L ( ψ ) ⊆ F L ( φ ) ⊆ F L (⟨ π ⟩ m φ ) and in the latter case use the inductive hypothesis (ii) to find F L ( ψ ) ⊆ F L ( ⟨ π ⟩ m φ ) FL(\psi) \subseteq FL(\langle\pi\rangle^{m}\varphi) F L ( ψ ) ⊆ F L (⟨ π ⟩ m φ ) .
Program induction. The atomic case a ∈ Π 0 a \in\Pi_0 a ∈ Π 0 is clear by F L ⋄ ( ⟨ a ⟩ m φ ) = { ⟨ a ⟩ m φ } FL^\diamond(\langle a\rangle^m\varphi)=\{\langle a\rangle^m\varphi\} F L ⋄ (⟨ a ⟩ m φ ) = {⟨ a ⟩ m φ } .
Case π 1 ∪ π 2 \pi_1 \cup\pi_2 π 1 ∪ π 2 : If ψ ∈ F L ⋄ ( ⟨ π 1 ∪ π 2 ⟩ m φ ) \psi\in FL^\diamond(\langle\pi_1 \cup\pi_2\rangle^m\varphi) ψ ∈ F L ⋄ (⟨ π 1 ∪ π 2 ⟩ m φ ) , then ψ = ⟨ π 1 ∪ π 2 ⟩ m φ \psi=\langle\pi_1\cup\pi_2\rangle^m\varphi ψ = ⟨ π 1 ∪ π 2 ⟩ m φ or ψ ∈ F L ⋄ ( ⟨ π 1 ⟩ m φ ) \psi\in FL^\diamond(\langle\pi_1\rangle^m\varphi) ψ ∈ F L ⋄ (⟨ π 1 ⟩ m φ ) or ψ ∈ F L ⋄ ( ⟨ π 2 ⟩ m φ ) \psi\in FL^\diamond(\langle\pi_2\rangle^m\varphi) ψ ∈ F L ⋄ (⟨ π 2 ⟩ m φ ) . In the first case the statement is clear and in the other two cases the inductive hypothesis on π j ∈ { π 1 , π 2 } \pi_j\in\{\pi_1,\pi_2\} π j ∈ { π 1 , π 2 } yields F L ( ψ ) ⊆ F L ( ⟨ π j ⟩ m φ ) ⊆ F L ( ⟨ π 1 ∪ π 2 ⟩ m φ ) FL(\psi)\subseteq FL(\langle\pi_j\rangle^m\varphi)\subseteq FL(\langle\pi_1\cup\pi_2\rangle^m\varphi) F L ( ψ ) ⊆ F L (⟨ π j ⟩ m φ ) ⊆ F L (⟨ π 1 ∪ π 2 ⟩ m φ ) .
Case π 1 ; π 2 \pi_1;\pi_2 π 1 ; π 2 : Suppose ψ ∈ F L ⋄ ( ⟨ π 1 ; π 2 ⟩ m φ ) \psi\in FL^\diamond(\langle\pi_1;\pi_2\rangle^m\varphi) ψ ∈ F L ⋄ (⟨ π 1 ; π 2 ⟩ m φ ) and ψ ≠ ⟨ π 1 ; π 2 ⟩ m φ \psi\ne\langle\pi_1;\pi_2\rangle^m\varphi ψ = ⟨ π 1 ; π 2 ⟩ m φ (otherwise the statement is clear). Then there is some i ∈ { 0 , … , m } i\in\{0,\ldots,m\} i ∈ { 0 , … , m } such that ψ ∈ F L ⋄ ( ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ ) \psi\in FL^\diamond(\langle\pi_1\rangle^{m-i}\langle\pi_2\rangle^i\varphi) ψ ∈ F L ⋄ (⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ ) or ψ ∈ F L ⋄ ( ⟨ π 2 ⟩ i φ ) \psi\in FL^\diamond(\langle\pi_2\rangle^i\varphi) ψ ∈ F L ⋄ (⟨ π 2 ⟩ i φ ) . In the former case use the inductive hypothesis on π 1 \pi_1 π 1 to obtain F L ( ψ ) ⊆ F L ( ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ ) ⊆ F L ( ⟨ π 1 ; π 2 ⟩ m φ ) FL(\psi)\subseteq FL(\langle\pi_1\rangle^{m-i}\langle\pi_2\rangle^i\varphi)\subseteq FL(\langle\pi_1;\pi_2\rangle^m\varphi) F L ( ψ ) ⊆ F L (⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i φ ) ⊆ F L (⟨ π 1 ; π 2 ⟩ m φ ) and in the latter case use the inductive hypothesis on π 2 \pi_2 π 2 to find F L ( ψ ) ⊆ F L ( ⟨ π 2 ⟩ i φ ) ⊆ F L ( ⟨ π 1 ; π 2 ⟩ m φ ) FL(\psi)\subseteq FL(\langle\pi_2\rangle^i\varphi)\subseteq FL(\langle\pi_1;\pi_2\rangle^m\varphi) F L ( ψ ) ⊆ F L (⟨ π 2 ⟩ i φ ) ⊆ F L (⟨ π 1 ; π 2 ⟩ m φ ) .
Case π ∗ \pi^* π ∗ : First note that by definition n ′ ≤ m n'\le m n ′ ≤ m implies F L ⋄ ( ⟨ π ∗ ⟩ n ′ φ ) ⊆ F L ⋄ ( ⟨ π ∗ ⟩ m φ ) FL^\diamond(\langle\pi^*\rangle^{n'}\varphi)\subseteq FL^\diamond(\langle\pi^*\rangle^m\varphi) F L ⋄ (⟨ π ∗ ⟩ n ′ φ ) ⊆ F L ⋄ (⟨ π ∗ ⟩ m φ ) . If ψ ∈ F L ⋄ ( ⟨ π ∗ ⟩ m φ ) \psi\in FL^\diamond(\langle\pi^*\rangle^m\varphi) ψ ∈ F L ⋄ (⟨ π ∗ ⟩ m φ ) , then there are n + n ′ ≤ m n+n'\le m n + n ′ ≤ m with ψ = ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ \psi=\langle\pi\rangle^n\langle\pi^*\rangle^{n'}\varphi ψ = ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ or ψ ∈ F L ⋄ ( ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) \psi\in FL^\diamond(\langle\pi\rangle^n\langle\pi^*\rangle^{n'}\varphi) ψ ∈ F L ⋄ (⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) . In the former case F L ( ψ ) ⊆ F L ( ⟨ π ∗ ⟩ m φ ) FL(\psi)\subseteq FL(\langle\pi^*\rangle^m\varphi) F L ( ψ ) ⊆ F L (⟨ π ∗ ⟩ m φ ) follows from the above observation and in the latter case use the inductive hypothesis on π \pi π to find F L ( ψ ) ⊆ F L ( ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) ⊆ F L ( ⟨ π ∗ ⟩ m φ ) FL(\psi)\subseteq FL(\langle\pi\rangle^n\langle\pi^*\rangle^{n'}\varphi)\subseteq FL(\langle\pi^*\rangle^m\varphi) F L ( ψ ) ⊆ F L (⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ φ ) ⊆ F L (⟨ π ∗ ⟩ m φ ) , where the last inclusion again uses the above observation.
Case ρ ? \rho? ρ ? : If ψ ∈ F L ⋄ ( ⟨ ρ ? ⟩ m φ ) \psi\in FL^\diamond(\langle\rho?\rangle^m\varphi) ψ ∈ F L ⋄ (⟨ ρ ? ⟩ m φ ) , then ψ = ⟨ ρ ⟩ m φ \psi=\langle\rho\rangle^m\varphi ψ = ⟨ ρ ⟩ m φ or ψ ∈ F L ( ρ ) \psi\in FL(\rho) ψ ∈ F L ( ρ ) . The former case is clear, in the latter case inductive hypothesis (i) on ρ \rho ρ yields F L ( ψ ) ⊆ F L ( ρ ) ⊆ F L ( ⟨ ρ ? ⟩ m φ ) FL(\psi)\subseteq FL(\rho)\subseteq FL(\langle\rho?\rangle^m\varphi) F L ( ψ ) ⊆ F L ( ρ ) ⊆ F L (⟨ ρ ? ⟩ m φ ) . □
With this, we get the following crucial closure rules of the Fischer-Ladner closure with respect to the program constructs of NPDL.
Corollary 3.5. For every formula φ \varphi φ , the set of formulas F L ( φ ) FL(\varphi) F L ( φ ) contains φ \varphi φ , is closed under subformulas and has the following additional closure properties.
(1) ⟨ π 1 ∪ π 2 ⟩ m ψ ∈ F L ( φ ) ⇒ ⟨ π 1 ⟩ m ψ ∈ F L ( φ ) \langle\pi_1\cup\pi_2\rangle^m\psi\in FL(\varphi)\Rightarrow\langle\pi_1\rangle^m\psi\in FL(\varphi) ⟨ π 1 ∪ π 2 ⟩ m ψ ∈ F L ( φ ) ⇒ ⟨ π 1 ⟩ m ψ ∈ F L ( φ ) & ⟨ π 2 ⟩ m ψ ∈ F L ( φ ) \langle\pi_2\rangle^m\psi\in FL(\varphi) ⟨ π 2 ⟩ m ψ ∈ F L ( φ ) ,
(2) ⟨ π 1 ; π 2 ⟩ m ψ ∈ F L ( φ ) ⇒ ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i ψ ∈ F L ( φ ) \langle\pi_1;\pi_2\rangle^m\psi\in FL(\varphi)\Rightarrow\langle\pi_1\rangle^{m-i}\langle\pi_2\rangle^i\psi\in FL(\varphi) ⟨ π 1 ; π 2 ⟩ m ψ ∈ F L ( φ ) ⇒ ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i ψ ∈ F L ( φ ) for all i ∈ { 0 , … , m } i\in\{0,\ldots,m\} i ∈ { 0 , … , m } ,
(3) ⟨ π ∗ ⟩ m ψ ∈ F L ( φ ) ⇒ ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ ψ ∈ F L ( φ ) \langle\pi^*\rangle^m\psi\in FL(\varphi)\Rightarrow\langle\pi\rangle^n\langle\pi^*\rangle^{n'}\psi\in FL(\varphi) ⟨ π ∗ ⟩ m ψ ∈ F L ( φ ) ⇒ ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ ψ ∈ F L ( φ ) for all n + n ′ ≤ m n+n'\le m n + n ′ ≤ m ,
(4) ⟨ ρ ? ⟩ m ψ ∈ F L ( φ ) ⇒ ρ ∈ F L ( φ ) \langle\rho?\rangle^m\psi\in FL(\varphi)\Rightarrow\rho\in FL(\varphi) ⟨ ρ ? ⟩ m ψ ∈ F L ( φ ) ⇒ ρ ∈ F L ( φ ) .
Proof. It is straightforward by Definition 3.1 to show (by mutual induction) that φ ′ ∈ F L ( φ ) \varphi'\in FL(\varphi) φ ′ ∈ F L ( φ ) for all subformulas φ ′ \varphi' φ ′ of φ \varphi φ and ⟨ π ⟩ m φ ∈ F L ⋄ ( ⟨ π ⟩ m φ ) \langle\pi\rangle^m\varphi\in FL^\diamond(\langle\pi\rangle^m\varphi) ⟨ π ⟩ m φ ∈ F L ⋄ (⟨ π ⟩ m φ ) always hold. With this, closure under subformulas easily follows from Lemma 3.4(i): If ψ ∈ F L ( φ ) \psi\in FL(\varphi) ψ ∈ F L ( φ ) and ψ ′ \psi' ψ ′ is a subformula of ψ \psi ψ , then ψ ′ ∈ F L ( ψ ) ⊆ F L ( φ ) \psi'\in FL(\psi)\subseteq FL(\varphi) ψ ′ ∈ F L ( ψ ) ⊆ F L ( φ ) . Conditions (1)–(4) also directly follow from the above fact together with Lemma 3.4(i), we prove (3) for the sake of illustration. If ⟨ π ∗ ⟩ m ψ ∈ F L ( φ ) \langle\pi^*\rangle^m\psi\in FL(\varphi) ⟨ π ∗ ⟩ m ψ ∈ F L ( φ ) then by Lemma 3.4(i) we find F L ⋄ ( ⟨ π ∗ ⟩ m ψ ) ⊆ F L ( φ ) FL^\diamond(\langle\pi^*\rangle^m\psi)\subseteq FL(\varphi) F L ⋄ (⟨ π ∗ ⟩ m ψ ) ⊆ F L ( φ ) . Therefore, we have ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ ψ ∈ F L ⋄ ( ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ ψ ) ⊆ F L ⋄ ( ⟨ π ∗ ⟩ m ψ ) ⊆ F L ( φ ) \langle\pi\rangle^n\langle\pi^*\rangle^{n'}\psi\in FL^\diamond(\langle\pi\rangle^n\langle\pi^*\rangle^{n'}\psi)\subseteq FL^\diamond(\langle\pi^*\rangle^m\psi)\subseteq FL(\varphi) ⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ ψ ∈ F L ⋄ (⟨ π ⟩ n ⟨ π ∗ ⟩ n ′ ψ ) ⊆ F L ⋄ (⟨ π ∗ ⟩ m ψ ) ⊆ F L ( φ ) as desired. □
In the next subsection, we show that NPDL has the bounded finite model property, by defining appropriate filtrations of models through the Fischer-Ladner closure.
Filtration and the Bounded Finite Model Property
In order to prove the bounded FMP (Corollary 3.8), we use filtrations similarly to standard PDL (e.g., see [10 Subsection 6.2] ). However, to accommodate for costs we need to define the appropriate weighted accessibility relations (also see many-valued PDL [20 Definition 4.3] ).
Definition 3.6 (Filtrations). Let M = ⟨ X , { R a } a ∈ Π 0 , V a l ⟩ \mathcal{M}=\langle X,\{R_a\}_{a\in\Pi_0},Val\rangle M = ⟨ X , { R a } a ∈ Π 0 , V a l ⟩ be a model and φ \varphi φ be a formula. The filtration of M \mathcal{M} M through F L ( φ ) FL(\varphi) F L ( φ ) is the model $\mathcal{M}^f_\varphi=\langle X^f,{R_a^f},Val^f\rangle
defined as follows. The set X f : = X / ↭ F L ( φ ) X^{f} := X/{\leftrightsquigarrow_{FL(\varphi)}} X f := X / ↭ F L ( φ ) is the quotient of X X X by the equivalence relation
x ↭ F L ( φ ) x ′ if and only if ∀ ψ ∈ F L ( φ ) : M , x ⊩ ψ ⇔ M , x ′ ⊩ ψ . x \leftrightsquigarrow_{FL(\varphi)} x' \quad\text{if and only if}\quad\forall\psi\in FL(\varphi): \mathcal{M},x \Vdash\psi\Leftrightarrow\mathcal{M},x' \Vdash\psi. x ↭ F L ( φ ) x ′ if and only if ∀ ψ ∈ F L ( φ ) : M , x ⊩ ψ ⇔ M , x ′ ⊩ ψ .
The weighted relations R a f : ( X f ) 2 → N ∞ R^{f}_{a} : (X^{f})^{2} \to\mathbb{N}^{\infty} R a f : ( X f ) 2 → N ∞ for a ∈ Π 0 a \in\Pi_{0} a ∈ Π 0 are defined via
R a f ( [ x ] , [ y ] ) = ⋀ { R a ( x ′ , y ′ ) ∣ x ′ ∈ [ x ] & y ′ ∈ [ y ] } . R^{f}_{a}([x],[y]) = \bigwedge\{R_{a}(x',y') \mid x' \in[x]\ \&\ y' \in[y]\}. R a f ([ x ] , [ y ]) = ⋀ { R a ( x ′ , y ′ ) ∣ x ′ ∈ [ x ] & y ′ ∈ [ y ]} .
The valuation is given by Val f ( p ) = { [ x ] ∣ M , x ⊩ p } \operatorname{Val}^{f}(p) = \{[x] \mid\mathcal{M},x \Vdash p\} Val f ( p ) = {[ x ] ∣ M , x ⊩ p } for p ∈ F L ( φ ) p \in FL(\varphi) p ∈ F L ( φ ) , otherwise Val f ( q ) = ∅ \operatorname{Val}^{f}(q) = \varnothing Val f ( q ) = ∅ .
We proceed with the central result of this subsection. The key ‘ingredients’ in the proof are the F L FL F L -closure properties of Corollary 3.5 together with the validities of Proposition 2.11.
Theorem 3.7 (Filtration Theorem). Let M φ f \mathcal{M}^{f}_{\varphi} M φ f be the filtration of the model M \mathcal{M} M as in Definition 3.6.
(i) For all formulas ψ \psi ψ with ψ ∈ F L ( φ ) \psi\in FL(\varphi) ψ ∈ F L ( φ ) it holds that M , x ⊩ ψ ⇔ M φ f , [ x ] ⊩ ψ \mathcal{M},x \Vdash\psi\Leftrightarrow\mathcal{M}^{f}_{\varphi},[x] \Vdash\psi M , x ⊩ ψ ⇔ M φ f , [ x ] ⊩ ψ .
(ii) For all programs π \pi π with ⟨ π ⟩ m ψ ∈ F L ( φ ) \langle\pi\rangle^{m}\psi\in FL(\varphi) ⟨ π ⟩ m ψ ∈ F L ( φ ) the following hold:
(a) R π f ( [ x ] , [ y ] ) ≤ R π ( x , y ) R^{f}_{\pi}([x],[y]) \le R_{\pi}(x,y) R π f ([ x ] , [ y ]) ≤ R π ( x , y ) ,
(b) If R π f ( [ x ] , [ y ] ) ≤ m R^{f}_{\pi}([x],[y]) \le m R π f ([ x ] , [ y ]) ≤ m and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ , then M , x ⊩ ⟨ π ⟩ m ψ \mathcal{M},x \Vdash\langle\pi\rangle^{m}\psi M , x ⊩ ⟨ π ⟩ m ψ .
Proof. Simultaneous induction on the formula ψ \psi ψ and program π \pi π (we abbreviate M f : = M φ f \mathcal{M}^{f} := \mathcal{M}^{f}_{\varphi} M f := M φ f ).
Formula induction. The base case p ∈ Φ 0 p \in\Phi_{0} p ∈ Φ 0 is covered by the definition of Val f \operatorname{Val}^{f} Val f and the cases ¬ ψ \neg\psi ¬ ψ and ψ 1 ∧ ψ 2 \psi_{1} \land\psi_{2} ψ 1 ∧ ψ 2 are standard induction arguments (note ¬ ψ ∈ F L ( φ ) ⇒ ψ ∈ F L ( φ ) \neg\psi\in FL(\varphi) \Rightarrow\psi\in FL(\varphi) ¬ ψ ∈ F L ( φ ) ⇒ ψ ∈ F L ( φ ) and ψ 1 ∧ ψ 2 ∈ F L ( φ ) ⇒ ψ 1 , ψ 2 ∈ F L ( φ ) \psi_{1} \land\psi_{2} \in FL(\varphi) \Rightarrow\psi_{1},\psi_{2} \in FL(\varphi) ψ 1 ∧ ψ 2 ∈ F L ( φ ) ⇒ ψ 1 , ψ 2 ∈ F L ( φ ) due to Corollary 3.5).
Case ⟨ π ⟩ m ψ \langle\pi\rangle^{m}\psi ⟨ π ⟩ m ψ : If M , x ⊩ ⟨ π ⟩ m ψ \mathcal{M},x \Vdash\langle\pi\rangle^{m}\psi M , x ⊩ ⟨ π ⟩ m ψ , then there is y ∈ X y \in X y ∈ X with R π ( x , y ) ≤ m R_{\pi}(x,y) \le m R π ( x , y ) ≤ m and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ . The inductive hypothesis (a) on π \pi π (note that we assume ⟨ π ⟩ m ψ ∈ F L ( φ ) \langle\pi\rangle^{m}\psi\in FL(\varphi) ⟨ π ⟩ m ψ ∈ F L ( φ ) ) gives R π f ( [ x ] , [ y ] ) ≤ R π ( x , y ) ≤ m R^{f}_{\pi}([x],[y]) \le R_{\pi}(x,y) \le m R π f ([ x ] , [ y ]) ≤ R π ( x , y ) ≤ m and the inductive hypothesis (i) on ψ \psi ψ (note that ψ ∈ F L ( φ ) \psi\in FL(\varphi) ψ ∈ F L ( φ ) by Corollary 3.5) gives M f , [ y ] ⊩ ψ \mathcal{M}^{f},[y] \Vdash\psi M f , [ y ] ⊩ ψ . We thus showed M f , [ x ] ⊩ ⟨ π ⟩ m ψ \mathcal{M}^{f},[x] \Vdash\langle\pi\rangle^{m}\psi M f , [ x ] ⊩ ⟨ π ⟩ m ψ as desired.
Conversely, if M f , [ x ] ⊩ ⟨ π ⟩ m ψ \mathcal{M}^{f},[x] \Vdash\langle\pi\rangle^{m}\psi M f , [ x ] ⊩ ⟨ π ⟩ m ψ , then there is [ y ] ∈ X f [y] \in X^{f} [ y ] ∈ X f such that R π f ( [ x ] , [ y ] ) ≤ m R^{f}_{\pi}([x],[y]) \le m R π f ([ x ] , [ y ]) ≤ m and M f , [ y ] ⊩ ψ \mathcal{M}^{f},[y] \Vdash\psi M f , [ y ] ⊩ ψ . From the inductive hypothesis (i) on ψ \psi ψ we get M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ and subsequently the inductive hypothesis (b) on π \pi π yields M , x ⊩ ⟨ π ⟩ m ψ \mathcal{M},x \Vdash\langle\pi\rangle^{m}\psi M , x ⊩ ⟨ π ⟩ m ψ as desired.
Program induction.
Case a ∈ Π 0 a \in\Pi_{0} a ∈ Π 0 : Let ⟨ a ⟩ m ψ ∈ F L ( φ ) \langle a\rangle^{m}\psi\in FL(\varphi) ⟨ a ⟩ m ψ ∈ F L ( φ ) . Condition (a) holds by Definition 3.6 since R a f ( [ x ] , [ y ] ) = ⋀ { R a ( x ′ , y ′ ) ∣ x ′ ∈ [ x ] & y ′ ∈ [ y ] } ≤ R a ( x , y ) R^{f}_{a}([x],[y]) = \bigwedge\{R_{a}(x',y') \mid x' \in[x]\ \&\ y' \in[y]\} \le R_{a}(x,y) R a f ([ x ] , [ y ]) = ⋀ { R a ( x ′ , y ′ ) ∣ x ′ ∈ [ x ] & y ′ ∈ [ y ]} ≤ R a ( x , y ) . For (b), suppose R a f ( [ x ] , [ y ] ) ≤ m R^{f}_{a}([x],[y]) \le m R a f ([ x ] , [ y ]) ≤ m and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ . The former means that there are x ′ ∈ [ x ] , y ′ ∈ [ y ] x' \in[x],y' \in[y] x ′ ∈ [ x ] , y ′ ∈ [ y ] such that R a ( x ′ , y ′ ) ≤ m R_{a}(x',y') \le m R a ( x ′ , y ′ ) ≤ m and the latter yields M , y ′ ⊩ ψ \mathcal{M},y' \Vdash\psi M , y ′ ⊩ ψ . Therefore, M , x ′ ⊩ ⟨ a ⟩ m ψ \mathcal{M},x' \Vdash\langle a\rangle^{m}\psi M , x ′ ⊩ ⟨ a ⟩ m ψ and since we assume ⟨ a ⟩ m ψ ∈ F L ( φ ) \langle a\rangle^{m}\psi\in FL(\varphi) ⟨ a ⟩ m ψ ∈ F L ( φ ) we lastly obtain M , x ⊩ ⟨ a ⟩ m ψ \mathcal{M},x \Vdash\langle a\rangle^{m}\psi M , x ⊩ ⟨ a ⟩ m ψ as needed.
R π 1 ∪ π 2 f ( [ x ] , [ y ] ) = R π 1 f ( [ x ] , [ y ] ) ∧ R π 2 f ( [ x ] , [ y ] ) ≤ R π 1 ( x , y ) ∧ R π 2 ( x , y ) = R π 1 ∪ π 2 ( x , y ) R^{f}_{\pi_{1}\cup\pi_{2}}([x],[y]) = R^{f}_{\pi_{1}}([x],[y]) \land R^{f}_{\pi_{2}}([x],[y])
\le R_{\pi_{1}}(x,y) \land R_{\pi_{2}}(x,y) = R_{\pi_{1}\cup\pi_{2}}(x,y) R π 1 ∪ π 2 f ([ x ] , [ y ]) = R π 1 f ([ x ] , [ y ]) ∧ R π 2 f ([ x ] , [ y ]) ≤ R π 1 ( x , y ) ∧ R π 2 ( x , y ) = R π 1 ∪ π 2 ( x , y )
by inductive hypothesis (a) on π 1 \pi_{1} π 1 and π 2 \pi_{2} π 2 (note that by Corollary 3.5(1) we have ⟨ π i ⟩ m ψ ∈ F L ( φ ) \langle\pi_{i}\rangle^{m}\psi\in FL(\varphi) ⟨ π i ⟩ m ψ ∈ F L ( φ ) ).
For (b), suppose R π 1 ∪ π 2 f ( [ x ] , [ y ] ) ≤ m R^{f}_{\pi_{1}\cup\pi_{2}}([x],[y]) \le m R π 1 ∪ π 2 f ([ x ] , [ y ]) ≤ m and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ . If R π 1 f ( [ x ] , [ y ] ) ≤ m R^{f}_{\pi_{1}}([x],[y]) \le m R π 1 f ([ x ] , [ y ]) ≤ m then the inductive hypothesis (b) on π 1 \pi_{1} π 1 yields M , x ⊩ ⟨ π 1 ⟩ m ψ \mathcal{M},x \Vdash\langle\pi_{1}\rangle^{m}\psi M , x ⊩ ⟨ π 1 ⟩ m ψ and thus also M , x ⊩ ⟨ π 1 ∪ π 2 ⟩ m ψ \mathcal{M},x \Vdash\langle\pi_{1}\cup\pi_{2}\rangle^{m}\psi M , x ⊩ ⟨ π 1 ∪ π 2 ⟩ m ψ by Proposition 2.11(4). If instead R π 2 f ( [ x ] , [ y ] ) ≤ m R^{f}_{\pi_{2}}([x],[y]) \le m R π 2 f ([ x ] , [ y ]) ≤ m , the argument is completely analogous.
⋀ [ v ] ∈ X f ( R π 1 f ( [ x ] , [ v ] ) + R π 2 f ( [ v ] , [ y ] ) ) ≤ ⋀ v ∈ X ( R π 1 ( x , v ) + R π 2 ( v , y ) ) \bigwedge_{[v]\in X^{f}} \left(R^{f}_{\pi_{1}}([x],[v]) + R^{f}_{\pi_{2}}([v],[y])\right)
\le\bigwedge_{v\in X} \left(R_{\pi_{1}}(x,v) + R_{\pi_{2}}(v,y)\right) [ v ] ∈ X f ⋀ ( R π 1 f ([ x ] , [ v ]) + R π 2 f ([ v ] , [ y ]) ) ≤ v ∈ X ⋀ ( R π 1 ( x , v ) + R π 2 ( v , y ) )
due to the inductive hypothesis ( a ) (a) ( a ) on π 1 \pi_1 π 1 and π 2 \pi_2 π 2 (note that by Corollary 3.5(2) we have ⟨ π 1 ⟩ m ⟨ π 2 ⟩ 0 ψ ∈ F L ( φ ) \langle\pi_1\rangle^m\langle\pi_2\rangle^0\psi\in FL(\varphi) ⟨ π 1 ⟩ m ⟨ π 2 ⟩ 0 ψ ∈ F L ( φ ) and by subformula closure ⟨ π 2 ⟩ 0 ψ ∈ F L ( φ ) \langle\pi_2\rangle^0\psi\in FL(\varphi) ⟨ π 2 ⟩ 0 ψ ∈ F L ( φ ) ).
For ( b ) (b) ( b ) , suppose R π 1 ; π 2 f ( [ x ] , [ y ] ) ≤ m R^f_{\pi_1;\pi_2}([x],[y]) \le m R π 1 ; π 2 f ([ x ] , [ y ]) ≤ m and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ . Due to the former, there exists [ v ] ∈ X f [v] \in X^f [ v ] ∈ X f such that R π 1 f ( [ x ] , [ v ] ) + R π 2 f ( [ v ] , [ y ] ) ≤ m R^f_{\pi_1}([x],[v])+R^f_{\pi_2}([v],[y]) \le m R π 1 f ([ x ] , [ v ]) + R π 2 f ([ v ] , [ y ]) ≤ m . Let i : = R π 2 f ( [ v ] , [ y ] ) i := R^f_{\pi_2}([v],[y]) i := R π 2 f ([ v ] , [ y ]) . Since R π 2 f ( [ v ] , [ y ] ) ≤ i R^f_{\pi_2}([v],[y]) \le i R π 2 f ([ v ] , [ y ]) ≤ i and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ , we can use the inductive hypothesis ( b ) (b) ( b ) on π 2 \pi_2 π 2 (note that by Corollary 3.5(2) we have ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i ψ ∈ F L ( φ ) \langle\pi_1\rangle^{m-i}\langle\pi_2\rangle^i\psi\in FL(\varphi) ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i ψ ∈ F L ( φ ) and ⟨ π 2 ⟩ i ψ ∈ F L ( φ ) \langle\pi_2\rangle^i\psi\in FL(\varphi) ⟨ π 2 ⟩ i ψ ∈ F L ( φ ) ) to obtain M , v ⊩ ⟨ π 2 ⟩ i ψ \mathcal{M},v \Vdash\langle\pi_2\rangle^i\psi M , v ⊩ ⟨ π 2 ⟩ i ψ . With R π 1 f ( [ x ] , [ v ] ) ≤ m − i R^f_{\pi_1}([x],[v]) \le m-i R π 1 f ([ x ] , [ v ]) ≤ m − i and the inductive hypothesis ( b ) (b) ( b ) on π 1 \pi_1 π 1 , this yields M , x ⊩ ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i ψ \mathcal{M},x \Vdash\langle\pi_1\rangle^{m-i}\langle\pi_2\rangle^i\psi M , x ⊩ ⟨ π 1 ⟩ m − i ⟨ π 2 ⟩ i ψ and therefore M , x ⊩ ⟨ π 1 ; π 2 ⟩ m ψ \mathcal{M},x \Vdash\langle\pi_1;\pi_2\rangle^m\psi M , x ⊩ ⟨ π 1 ; π 2 ⟩ m ψ by Proposition 2.11(5).
Case π ∗ \pi^* π ∗ : Let ⟨ π ∗ ⟩ m ψ ∈ F L ( φ ) \langle\pi^*\rangle^m\psi\in FL(\varphi) ⟨ π ∗ ⟩ m ψ ∈ F L ( φ ) . For ( a ) (a) ( a ) it suffices to show ( R π f ) [ k ] ( [ x ] , [ y ] ) ≤ ( R π ) [ k ] ( x , y ) (R^f_\pi)^{[k]}([x],[y]) \le(R_\pi)^{[k]}(x,y) ( R π f ) [ k ] ([ x ] , [ y ]) ≤ ( R π ) [ k ] ( x , y ) for all k ≥ 0 k \ge0 k ≥ 0 , which is done by induction. The case k = 0 k=0 k = 0 is straightforward and for the inductive step k ↦ k + 1 k \mapsto k+1 k ↦ k + 1 similarly to the case of composition above, one uses
⋀ [ v ] ∈ X f R π f ( [ x ] , [ v ] ) + ( R π f ) [ k ] ( [ v ] , [ y ] ) ≤ ⋀ v ∈ X R π ( x , v ) + ( R π ) [ k ] ( v , y ) \bigwedge_{[v]\in X^f} R^f_\pi([x],[v])+(R^f_\pi)^{[k]}([v],[y]) \le\bigwedge_{v\in X} R_\pi(x,v)+(R_\pi)^{[k]}(v,y) [ v ] ∈ X f ⋀ R π f ([ x ] , [ v ]) + ( R π f ) [ k ] ([ v ] , [ y ]) ≤ v ∈ X ⋀ R π ( x , v ) + ( R π ) [ k ] ( v , y )
which follows from the inductive hypothesis on k k k and inductive hypothesis ( a ) (a) ( a ) on π \pi π (note that by Corollary 3.5(3) we have ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 ψ ∈ F L ( φ ) \langle\pi\rangle^m\langle\pi^*\rangle^0\psi\in FL(\varphi) ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 ψ ∈ F L ( φ ) ).
For ( b ) (b) ( b ) , suppose R π ∗ f ( [ x ] , [ y ] ) ≤ m R^f_{\pi^*}([x],[y]) \le m R π ∗ f ([ x ] , [ y ]) ≤ m and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ . By the former, ( R π f ) [ k ] ( [ x ] , [ y ] ) ≤ m (R^f_\pi)^{[k]}([x],[y]) \le m ( R π f ) [ k ] ([ x ] , [ y ]) ≤ m for some k ≥ 0 k \ge0 k ≥ 0 . If ( R π f ) [ 0 ] ( [ x ] , [ y ] ) ≤ m (R^f_\pi)^{[0]}([x],[y]) \le m ( R π f ) [ 0 ] ([ x ] , [ y ]) ≤ m then [ x ] = [ y ] [x]=[y] [ x ] = [ y ] implies M , x ⊩ ψ \mathcal{M},x \Vdash\psi M , x ⊩ ψ implies M , x ⊩ ⟨ π ∗ ⟩ m ψ \mathcal{M},x \Vdash\langle\pi^*\rangle^m\psi M , x ⊩ ⟨ π ∗ ⟩ m ψ . If ( R π f ) [ 1 ] ( [ x ] , [ y ] ) ≤ m (R^f_\pi)^{[1]}([x],[y]) \le m ( R π f ) [ 1 ] ([ x ] , [ y ]) ≤ m note that M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ implies M , y ⊩ ⟨ π ∗ ⟩ 0 ψ \mathcal{M},y \Vdash\langle\pi^*\rangle^0\psi M , y ⊩ ⟨ π ∗ ⟩ 0 ψ and we use the inductive hypothesis ( b ) (b) ( b ) on π \pi π (note that by Corollary 3.5(3) we have ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 ψ ∈ F L ( φ ) \langle\pi\rangle^m\langle\pi^*\rangle^0\psi\in FL(\varphi) ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 ψ ∈ F L ( φ ) ) to obtain M , x ⊩ ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 ψ \mathcal{M},x \Vdash\langle\pi\rangle^m\langle\pi^*\rangle^0\psi M , x ⊩ ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 ψ which implies M , x ⊩ ⟨ π ∗ ⟩ m ψ \mathcal{M},x \Vdash\langle\pi^*\rangle^m\psi M , x ⊩ ⟨ π ∗ ⟩ m ψ by Proposition 2.11(6). If k ≥ 2 k \ge2 k ≥ 2 then there are states v 1 , … , v k − 1 ∈ X v_1,\ldots,v_{k-1}\in X v 1 , … , v k − 1 ∈ X such that
m 1 + m 2 + ⋯ + m k : = R π f ( [ x ] , [ v 1 ] ) + R π f ( [ v 1 ] , [ v 2 ] ) + ⋯ + R π f ( [ v k ] , [ y ] ) ≤ m . m_1+m_2+\cdots+m_k := R^f_\pi([x],[v_1])+R^f_\pi([v_1],[v_2])+\cdots+R^f_\pi([v_k],[y]) \le m. m 1 + m 2 + ⋯ + m k := R π f ([ x ] , [ v 1 ]) + R π f ([ v 1 ] , [ v 2 ]) + ⋯ + R π f ([ v k ] , [ y ]) ≤ m .
We again have M , y ⊩ ⟨ π ∗ ⟩ 0 ψ \mathcal{M},y \Vdash\langle\pi^*\rangle^0\psi M , y ⊩ ⟨ π ∗ ⟩ 0 ψ and since R π f ( [ v k − 1 ] , [ y ] ) ≤ m k R^f_\pi([v_{k-1}],[y]) \le m_k R π f ([ v k − 1 ] , [ y ]) ≤ m k together with the inductive hypothesis ( b ) (b) ( b ) on π \pi π (note that by Corollary 3.5(3) we have ⟨ π ⟩ m k ⟨ π ∗ ⟩ 0 ψ ∈ F L ( φ ) \langle\pi\rangle^{m_k}\langle\pi^*\rangle^0\psi\in FL(\varphi) ⟨ π ⟩ m k ⟨ π ∗ ⟩ 0 ψ ∈ F L ( φ ) ) we get M , v k − 1 ⊩ ⟨ π ⟩ m k ⟨ π ∗ ⟩ 0 ψ \mathcal{M},v_{k-1} \Vdash\langle\pi\rangle^{m_k}\langle\pi^*\rangle^0\psi M , v k − 1 ⊩ ⟨ π ⟩ m k ⟨ π ∗ ⟩ 0 ψ , which implies M , v k − 1 ⊩ ⟨ π ∗ ⟩ m k ψ \mathcal{M},v_{k-1} \Vdash\langle\pi^*\rangle^{m_k}\psi M , v k − 1 ⊩ ⟨ π ∗ ⟩ m k ψ . Using R π f ( [ v k − 2 ] , [ v k − 1 ] ) ≤ m k − 1 R^f_\pi([v_{k-2}],[v_{k-1}]) \le m_{k-1} R π f ([ v k − 2 ] , [ v k − 1 ]) ≤ m k − 1 and the inductive hypothesis ( b ) (b) ( b ) on π \pi π (note that ⟨ π ⟩ m k − 1 ⟨ π ∗ ⟩ m k ψ ∈ F L ( φ ) \langle\pi\rangle^{m_{k-1}}\langle\pi^*\rangle^{m_k}\psi\in FL(\varphi) ⟨ π ⟩ m k − 1 ⟨ π ∗ ⟩ m k ψ ∈ F L ( φ ) ) we get M , v k − 2 ⊩ ⟨ π ⟩ m k − 1 ⟨ π ∗ ⟩ m k ψ \mathcal{M},v_{k-2} \Vdash\langle\pi\rangle^{m_{k-1}}\langle\pi^*\rangle^{m_k}\psi M , v k − 2 ⊩ ⟨ π ⟩ m k − 1 ⟨ π ∗ ⟩ m k ψ , which implies that M , v k − 2 ⊩ ⟨ π ∗ ⟩ m k − 1 + m k ψ \mathcal{M},v_{k-2} \Vdash\langle\pi^*\rangle^{m_{k-1}+m_k}\psi M , v k − 2 ⊩ ⟨ π ∗ ⟩ m k − 1 + m k ψ . Proceeding like this (note ⟨ π ⟩ m j ⟨ π ∗ ⟩ m j + 1 + ⋯ + m k ψ ∈ F L ( φ ) \langle\pi\rangle^{m_j}\langle\pi^*\rangle^{m_{j+1}+\cdots+m_k}\psi\in FL(\varphi) ⟨ π ⟩ m j ⟨ π ∗ ⟩ m j + 1 + ⋯ + m k ψ ∈ F L ( φ ) for all 1 ≤ j ≤ k 1 \le j \le k 1 ≤ j ≤ k ), we eventually arrive at M , x ⊩ ⟨ π ∗ ⟩ m 1 + ⋯ + m k ψ \mathcal{M},x \Vdash\langle\pi^*\rangle^{m_1+\cdots+m_k}\psi M , x ⊩ ⟨ π ∗ ⟩ m 1 + ⋯ + m k ψ , which by Proposition 2.11(3) implies M , x ⊩ ⟨ π ∗ ⟩ m ψ \mathcal{M},x \Vdash\langle\pi^*\rangle^m\psi M , x ⊩ ⟨ π ∗ ⟩ m ψ as desired.
Case ρ ? \rho? ρ ? : To see ( a ) (a) ( a ) recall that R ρ ? ( x , y ) = 0 R_{\rho?}(x,y)=0 R ρ ? ( x , y ) = 0 if and only if x = y x=y x = y and M , x ⊩ ρ \mathcal{M},x \Vdash\rho M , x ⊩ ρ (otherwise ( a ) (a) ( a ) is trivial as R ρ ? ( x , y ) = ∞ R_{\rho?}(x,y)=\infty R ρ ? ( x , y ) = ∞ ). By the inductive hypothesis ( i ) (i) ( i ) on ρ \rho ρ (note that by Corollary 3.5(4) we have ρ ∈ F L ( φ ) \rho\in FL(\varphi) ρ ∈ F L ( φ ) ) this implies M f , [ x ] ⊩ ρ \mathcal{M}^f,[x] \Vdash\rho M f , [ x ] ⊩ ρ and thus R ρ ? f ( [ x ] , [ y ] ) = 0 R^f_{\rho?}([x],[y])=0 R ρ ? f ([ x ] , [ y ]) = 0 .
For ( b ) (b) ( b ) , let R ρ ? f ( [ x ] , [ y ] ) ≤ m R^f_{\rho?}([x],[y]) \le m R ρ ? f ([ x ] , [ y ]) ≤ m and M , y ⊩ ψ \mathcal{M},y \Vdash\psi M , y ⊩ ψ . The former yields R ρ ? f ( [ x ] , [ y ] ) = 0 R^f_{\rho?}([x],[y])=0 R ρ ? f ([ x ] , [ y ]) = 0 , which holds if and only if [ x ] = [ y ] [x]=[y] [ x ] = [ y ] and M f , [ y ] ⊩ ρ \mathcal{M}^f,[y] \Vdash\rho M f , [ y ] ⊩ ρ . By inductive hypothesis ( i ) (i) ( i ) on ρ \rho ρ this implies M , y ⊩ ρ \mathcal{M},y \Vdash\rho M , y ⊩ ρ . Thus M , y ⊩ ρ ∧ ψ \mathcal{M},y \Vdash\rho\land\psi M , y ⊩ ρ ∧ ψ , which is equivalent to M , y ⊩ ⟨ ρ ? ⟩ m ψ \mathcal{M},y \Vdash\langle\rho?\rangle^m\psi M , y ⊩ ⟨ ρ ? ⟩ m ψ by Proposition 2.11(7). □
The bounded finite model property now easily follows.
Corollary 3.8 (Bounded FMP). The NPDL-formula φ \varphi φ is satisfiable if and only if it is satisfiable in some finite model of size at most 2 ∥ φ ∥ 2^{\|\varphi\|} 2 ∥ φ ∥ .
Proof. If φ \varphi φ is satisfied in a model M \mathcal{M} M , then as a consequence of Theorem 3.7 it is also satisfied in the filtration M φ f \mathcal{M}^f_\varphi M φ f . By Lemma 3.3 we know ∣ F L ( φ ) ∣ ≤ ∥ φ ∥ |FL(\varphi)| \le\|\varphi\| ∣ F L ( φ ) ∣ ≤ ∥ φ ∥ and it is easy to see that ∣ X f ∣ ≤ 2 ∣ F L ( φ ) ∣ |X^f| \le2^{|FL(\varphi)|} ∣ X f ∣ ≤ 2 ∣ F L ( φ ) ∣ by Definition 3.6 (since [ x ] ↦ { ψ ∈ F L ( φ ) ∣ M , x ⊩ ψ } [x] \mapsto\{\psi\in FL(\varphi)\mid\mathcal{M},x \Vdash\psi\} [ x ] ↦ { ψ ∈ F L ( φ ) ∣ M , x ⊩ ψ } is injective). □
However, unlike in standard PDL, this does not immediately yield decidability. Indeed, since we interpret formulas on N ∞ \mathbb{N}^{\infty} N ∞ -weighted graphs, there are still infinitely many ‘candidates’ for weights of atomic programs R a R_a R a , even on a finite set. Therefore, we need to show that there also exists a bound on weights sufficient to check the satisfiability of a formula.
Bounding Weights
In this subsection, for every formula φ \varphi φ we aim to find a natural number N ( φ ) N(\varphi) N ( φ ) such that satisfiability of φ \varphi φ can be checked by only considering models with R a : X 2 → { 0 , 1 , … , N ( φ ) + 1 } R_a : X^2 \to\{0,1,\ldots,N(\varphi)+1\} R a : X 2 → { 0 , 1 , … , N ( φ ) + 1 } for all atomic programs. Note that together with the bounded finite model property proved in the previous subsection (Corollary 3.8), this will establish decidability.
Intuitively, the bound N ( φ ) N(\varphi) N ( φ ) is the largest m m m for which some expression of the form ⟨ π ⟩ m \langle\pi\rangle^m ⟨ π ⟩ m appears (anywhere) in the formula φ \varphi φ . We make this precise in the following.
Definition 3.9. By mutual induction on the formula φ ∈ Φ \varphi\in\Phi φ ∈ Φ and the program π ∈ Π \pi\in\Pi π ∈ Π , we define the natural numbers N ( φ ) N(\varphi) N ( φ ) and N ( π ) N(\pi) N ( π ) as follows.
Formulas:
N ( p ) = 0 N(p)=0 N ( p ) = 0 for p ∈ Φ 0 p \in\Phi_0 p ∈ Φ 0 ,
N ( ¬ φ ) = N ( φ ) N(\neg\varphi)=N(\varphi) N ( ¬ φ ) = N ( φ ) ,
N ( φ 1 ∧ φ 2 ) = max { N ( φ 1 ) , N ( φ 2 ) } N(\varphi_1 \land\varphi_2)=\max\{N(\varphi_1),N(\varphi_2)\} N ( φ 1 ∧ φ 2 ) = max { N ( φ 1 ) , N ( φ 2 )} ,
N ( ⟨ π ⟩ m φ ) = max { m , N ( φ ) , N ( π ) } N(\langle\pi\rangle^m\varphi)=\max\{m,N(\varphi),N(\pi)\} N (⟨ π ⟩ m φ ) = max { m , N ( φ ) , N ( π )} .
Programs:
N ( a ) = 0 N(a)=0 N ( a ) = 0 for a ∈ Π 0 a \in\Pi_0 a ∈ Π 0 ,
N ( π 1 ∪ π 2 ) = max { N ( π 1 ) , N ( π 2 ) } N(\pi_1\cup\pi_2)=\max\{N(\pi_1),N(\pi_2)\} N ( π 1 ∪ π 2 ) = max { N ( π 1 ) , N ( π 2 )} ,
N ( π 1 ; π 2 ) = max { N ( π 1 ) , N ( π 2 ) } N(\pi_1;\pi_2)=\max\{N(\pi_1),N(\pi_2)\} N ( π 1 ; π 2 ) = max { N ( π 1 ) , N ( π 2 )} ,
N ( π ∗ ) = N ( π ) N(\pi^*)=N(\pi) N ( π ∗ ) = N ( π ) ,
N ( φ ? ) = N ( φ ) N(\varphi?)=N(\varphi) N ( φ ?) = N ( φ ) .
(Since all maxima range over finite sets, these are well-defined natural numbers.)
The idea now is to turn a model into a model where only finitely many weights appear by ‘cutting off’ all weights which go beyond a certain ‘threshold’.
Definition 3.10 (Cut-off models). Let M = ⟨ X , { R a } a ∈ Π 0 , V a l ⟩ \mathcal{M}=\langle X,\{R_a\}_{a\in\Pi_0},\mathrm{Val}\rangle M = ⟨ X , { R a } a ∈ Π 0 , Val ⟩ be a model and n ∈ N n\in\mathbb{N} n ∈ N . The corresponding n n n -cut-off model M n = ⟨ X , { R a n } a ∈ Π 0 , V a l ⟩ \mathcal{M}^n=\langle X,\{R_a^n\}_{a\in\Pi_0},\mathrm{Val}\rangle M n = ⟨ X , { R a n } a ∈ Π 0 , Val ⟩ is defined by R a n ( x , y ) = R a ( x , y ) ∧ n R_a^n(x,y)=R_a(x,y)\wedge n R a n ( x , y ) = R a ( x , y ) ∧ n .
The main technical result of this subsection shows that satisfiability of φ \varphi φ stays preserved as long as the cut-off happens (strictly) above N ( φ ) N(\varphi) N ( φ ) .
Proposition 3.11. Let M \mathcal{M} M be a model and { M n } n ∈ N \{\mathcal{M}^n\}_{n\in\mathbb{N}} { M n } n ∈ N be the cut-off models as in Definition 3.10.
(i) For all formulas φ ∈ Φ \varphi\in\Phi φ ∈ Φ : ( M , x ⊩ φ ⟺ M n , x ⊩ φ ) (\mathcal{M},x\Vdash\varphi\Longleftrightarrow\mathcal{M}^n,x\Vdash\varphi) ( M , x ⊩ φ ⟺ M n , x ⊩ φ ) for all n > N ( φ ) n>N(\varphi) n > N ( φ ) .
(ii) For all programs π ∈ Π \pi\in\Pi π ∈ Π : ( R π ( x , y ) ∧ n = R π n ( x , y ) ∧ n ) (R_\pi(x,y)\wedge n=R_\pi^n(x,y)\wedge n) ( R π ( x , y ) ∧ n = R π n ( x , y ) ∧ n ) for all n > N ( π ) n>N(\pi) n > N ( π ) .
Proof. Simultaneous induction on the formula φ \varphi φ and the program π \pi π .
Formula induction. The base case p ∈ Φ 0 p\in\Phi_0 p ∈ Φ 0 is immediate from V a l n = V a l \mathrm{Val}^n=\mathrm{Val} Val n = Val and the cases ¬ φ \neg\varphi ¬ φ and φ 1 ∧ φ 2 \varphi_1\land\varphi_2 φ 1 ∧ φ 2 are easily obtained from the corresponding inductive hypotheses (i) on φ \varphi φ and φ 1 , φ 2 \varphi_1,\varphi_2 φ 1 , φ 2 , respectively (recall N ( ¬ φ ) = N ( φ ) N(\neg\varphi)=N(\varphi) N ( ¬ φ ) = N ( φ ) and N ( φ 1 ∧ φ 2 ) ≥ N ( φ i ) N(\varphi_1\land\varphi_2)\geq N(\varphi_i) N ( φ 1 ∧ φ 2 ) ≥ N ( φ i ) ).
Case ⟨ π ⟩ m φ \langle\pi\rangle^m\varphi ⟨ π ⟩ m φ : Let n > N ( ⟨ π ⟩ m φ ) n>N(\langle\pi\rangle^m\varphi) n > N (⟨ π ⟩ m φ ) . Then M , x ⊩ ⟨ π ⟩ m φ \mathcal{M},x\Vdash\langle\pi\rangle^m\varphi M , x ⊩ ⟨ π ⟩ m φ if and only if there is y ∈ X y\in X y ∈ X with M , y ⊩ φ \mathcal{M},y\Vdash\varphi M , y ⊩ φ and R π ( x , y ) ≤ m R_\pi(x,y)\leq m R π ( x , y ) ≤ m . By inductive hypothesis (i) on φ \varphi φ (note n > N ( φ ) n>N(\varphi) n > N ( φ ) ) we have
M , y ⊩ φ if and only if M n , y ⊩ φ \mathcal{M},y\Vdash\varphi\ \text{if and only if}\ \mathcal{M}^n,y\Vdash\varphi M , y ⊩ φ if and only if M n , y ⊩ φ
and by the inductive hypothesis ( i i ) (ii) ( ii ) on π \pi π (note n > N ( π ) n > N(\pi) n > N ( π ) ) and the fact that n > m n > m n > m we have
R π ( x , y ) ≤ m if and only if R π n ( x , y ) ≤ m . R_{\pi}(x,y) \leq m \text{ if and only if } R_{\pi}^{n}(x,y) \leq m. R π ( x , y ) ≤ m if and only if R π n ( x , y ) ≤ m .
Thus M , x ⊩ ⟨ π ⟩ m φ \mathcal{M},x \Vdash\langle\pi\rangle^{m}\varphi M , x ⊩ ⟨ π ⟩ m φ if and only if there exists some y ∈ X y \in X y ∈ X with M n , y ⊩ φ \mathcal{M}^{n},y \Vdash\varphi M n , y ⊩ φ and R π n ( x , y ) ≤ m R_{\pi}^{n}(x,y) \leq m R π n ( x , y ) ≤ m , which by definition is equivalent to M n , x ⊩ ⟨ π ⟩ m φ \mathcal{M}^{n},x \Vdash\langle\pi\rangle^{m}\varphi M n , x ⊩ ⟨ π ⟩ m φ .
Program induction. For the base case a ∈ Π 0 a \in\Pi_{0} a ∈ Π 0 , by Definition 3.10 we have R a n ( x , y ) = R a ( x , y ) ∧ n R_{a}^{n}(x,y)=R_{a}(x,y)\wedge n R a n ( x , y ) = R a ( x , y ) ∧ n and thus R a n ( x , y ) ∧ n = R a ( x , y ) ∧ n R_{a}^{n}(x,y)\wedge n=R_{a}(x,y)\wedge n R a n ( x , y ) ∧ n = R a ( x , y ) ∧ n .
Case π 1 ∪ π 2 \pi_{1}\cup\pi_{2} π 1 ∪ π 2 : Let n > N ( π 1 ∪ π 2 ) = max { N ( π 1 ) , N ( π 2 ) } n>N(\pi_{1}\cup\pi_{2})=\max\{N(\pi_{1}),N(\pi_{2})\} n > N ( π 1 ∪ π 2 ) = max { N ( π 1 ) , N ( π 2 )} . We compute
R π 1 ∪ π 2 ( x , y ) ∧ n = R π 1 ( x , y ) ∧ R π 2 ( x , y ) ∧ n = ( R π 1 ( x , y ) ∧ n ) ∧ ( R π 2 ( x , y ) ∧ n ) = ( R π 1 n ( x , y ) ∧ n ) ∧ ( R π 2 n ( x , y ) ∧ n ) = R π 1 n ( x , y ) ∧ R π 2 n ( x , y ) ∧ n = R π 1 ∪ π 2 n ( x , y ) ∧ n , \begin{aligned}
R_{\pi_{1}\cup\pi_{2}}(x,y)\wedge n
&=R_{\pi_{1}}(x,y)\wedge R_{\pi_{2}}(x,y)\wedge n\\
&=(R_{\pi_{1}}(x,y)\wedge n)\wedge(R_{\pi_{2}}(x,y)\wedge n)\\
&=(R_{\pi_{1}}^{n}(x,y)\wedge n)\wedge(R_{\pi_{2}}^{n}(x,y)\wedge n)\\
&=R_{\pi_{1}}^{n}(x,y)\wedge R_{\pi_{2}}^{n}(x,y)\wedge n
=R_{\pi_{1}\cup\pi_{2}}^{n}(x,y)\wedge n,
\end{aligned} R π 1 ∪ π 2 ( x , y ) ∧ n = R π 1 ( x , y ) ∧ R π 2 ( x , y ) ∧ n = ( R π 1 ( x , y ) ∧ n ) ∧ ( R π 2 ( x , y ) ∧ n ) = ( R π 1 n ( x , y ) ∧ n ) ∧ ( R π 2 n ( x , y ) ∧ n ) = R π 1 n ( x , y ) ∧ R π 2 n ( x , y ) ∧ n = R π 1 ∪ π 2 n ( x , y ) ∧ n ,
where the third equality uses the inductive hypothesis ( i i ) (ii) ( ii ) on π 1 \pi_{1} π 1 and π 2 \pi_{2} π 2 (note n > N ( π i ) n>N(\pi_{i}) n > N ( π i ) ).
Case π 1 ; π 2 \pi_{1};\pi_{2} π 1 ; π 2 : Let n > N ( π 1 ; π 2 ) = max { N ( π 1 ) , N ( π 2 ) } n>N(\pi_{1};\pi_{2})=\max\{N(\pi_{1}),N(\pi_{2})\} n > N ( π 1 ; π 2 ) = max { N ( π 1 ) , N ( π 2 )} . We compute
R π 1 ; π 2 ( x , y ) ∧ n = ( ⋀ v ∈ X R π 1 ( x , v ) + R π 2 ( v , y ) ) ∧ n = ⋀ v ∈ X ( ( R π 1 ( x , v ) ∧ n ) + ( R π 2 ( v , y ) ∧ n ) ) ∧ n = ⋀ v ∈ X ( ( R π 1 n ( x , v ) ∧ n ) + ( R π 2 n ( v , y ) ∧ n ) ) ∧ n = ( ⋀ v ∈ X R π 1 n ( x , v ) + R π 2 n ( v , y ) ) ∧ n = R π 1 ; π 2 n ( x , y ) ∧ n , \begin{aligned}
R_{\pi_{1};\pi_{2}}(x,y)\wedge n
&=\left(\bigwedge_{v\in X}R_{\pi_{1}}(x,v)+R_{\pi_{2}}(v,y)\right)\wedge n\\
&=\bigwedge_{v\in X}\left((R_{\pi_{1}}(x,v)\wedge n)+(R_{\pi_{2}}(v,y)\wedge n)\right)\wedge n\\
&=\bigwedge_{v\in X}\left((R_{\pi_{1}}^{n}(x,v)\wedge n)+(R_{\pi_{2}}^{n}(v,y)\wedge n)\right)\wedge n\\
&=\left(\bigwedge_{v\in X}R_{\pi_{1}}^{n}(x,v)+R_{\pi_{2}}^{n}(v,y)\right)\wedge n
=R_{\pi_{1};\pi_{2}}^{n}(x,y)\wedge n,
\end{aligned} R π 1 ; π 2 ( x , y ) ∧ n = ( v ∈ X ⋀ R π 1 ( x , v ) + R π 2 ( v , y ) ) ∧ n = v ∈ X ⋀ ( ( R π 1 ( x , v ) ∧ n ) + ( R π 2 ( v , y ) ∧ n ) ) ∧ n = v ∈ X ⋀ ( ( R π 1 n ( x , v ) ∧ n ) + ( R π 2 n ( v , y ) ∧ n ) ) ∧ n = ( v ∈ X ⋀ R π 1 n ( x , v ) + R π 2 n ( v , y ) ) ∧ n = R π 1 ; π 2 n ( x , y ) ∧ n ,
the third ‘= = = ’ uses inductive hypothesis ( i i ) (ii) ( ii ) on π 1 , π 2 \pi_{1},\pi_{2} π 1 , π 2 (note n > N ( π i ) n>N(\pi_{i}) n > N ( π i ) ), the second and fourth ones use the laws ( ⋀ b i ) ∧ n = ⋀ ( b i ∧ n ) (\bigwedge b_{i})\wedge n=\bigwedge(b_{i}\wedge n) ( ⋀ b i ) ∧ n = ⋀ ( b i ∧ n ) and ( c + d ) ∧ n = ( c ∧ n ) + ( d ∧ n ) ∧ n (c+d)\wedge n=(c\wedge n)+(d\wedge n)\wedge n ( c + d ) ∧ n = ( c ∧ n ) + ( d ∧ n ) ∧ n in N ∞ \mathbb{N}^{\infty} N ∞ .
Case π ∗ \pi^{*} π ∗ : Let n > N ( π ∗ ) = N ( π ) n>N(\pi^{*})=N(\pi) n > N ( π ∗ ) = N ( π ) . It suffices to show that ( R π ) [ k ] ( x , y ) ∧ n = ( R π n ) [ k ] ( x , y ) ∧ n (R_{\pi})^{[k]}(x,y)\wedge n=(R_{\pi}^{n})^{[k]}(x,y)\wedge n ( R π ) [ k ] ( x , y ) ∧ n = ( R π n ) [ k ] ( x , y ) ∧ n holds for all k ≥ 0 k\geq0 k ≥ 0 , which is done by induction. The base case k = 0 k=0 k = 0 is obvious since ( R π ) [ 0 ] = ( R π n ) [ 0 ] (R_{\pi})^{[0]}=(R_{\pi}^{n})^{[0]} ( R π ) [ 0 ] = ( R π n ) [ 0 ] and the inductive step k ↦ k + 1 k\mapsto k+1 k ↦ k + 1 is similar to the case of sequential composition ; ; ; above, using the inductive hypotheses on k k k and on π \pi π (note n > N ( π ) n>N(\pi) n > N ( π ) ).
R ψ ? ( x , y ) = { 0 if x = y & M , x ⊩ ψ , ∞ otherwise . R_{\psi?}(x,y)=
\begin{cases}
0 & \text{if }x=y\ \&\ \mathcal{M},x\Vdash\psi,\\
\infty& \text{otherwise}.
\end{cases} R ψ ? ( x , y ) = { 0 ∞ if x = y & M , x ⊩ ψ , otherwise .
and
R ψ ? n ( x , y ) = { 0 if x = y & M n , x ⊩ ψ , ∞ otherwise . R_{\psi?}^{n}(x,y)=
\begin{cases}
0 & \text{if }x=y\ \&\ \mathcal{M}^{n},x\Vdash\psi,\\
\infty& \text{otherwise}.
\end{cases} R ψ ? n ( x , y ) = { 0 ∞ if x = y & M n , x ⊩ ψ , otherwise .
By the inductive hypothesis ( i ) (i) ( i ) on ψ \psi ψ (note n > N ( ψ ) n>N(\psi) n > N ( ψ ) ) we have M , x ⊩ ψ \mathcal{M},x\Vdash\psi M , x ⊩ ψ if and only if M n , x ⊩ ψ \mathcal{M}^{n},x\Vdash\psi M n , x ⊩ ψ , showing R ψ ? = R ψ ? n R_{\psi?}=R_{\psi?}^{n} R ψ ? = R ψ ? n which trivially implies R ψ ? ∧ n = R ψ ? n ∧ n R_{\psi?}\wedge n=R_{\psi?}^{n}\wedge n R ψ ? ∧ n = R ψ ? n ∧ n . □
Combining the bounded finite model property (Corollary 3.8) and the previous result about the bound on weights yields the following.
Theorem 3.12 (Decidability). Satisfiability and validity of NPDL are decidable.
Proof. Let φ \varphi φ be a formula. By the bounded finite model property (Corollary 3.8) φ \varphi φ and Proposition 3.11, φ \varphi φ is satisfiable if and only if it is satisfiable in a finite model of size at most 2 ∥ φ ∥ N 2^{\lVert\varphi\rVert_{N}} 2 ∥ φ ∥ N where the weights of atomic programs only take values in { 0 , 1 , … , N ( φ ) + 1 } \{0,1,\ldots,N(\varphi)+1\} { 0 , 1 , … , N ( φ ) + 1 } . Lastly, note that only the finitely many propositional variables and atomic programs (plus finitely many complex programs computed from these) occurring in φ \varphi φ are ‘relevant’ to check satisfiability. The fact that validity of φ \varphi φ is decidable follows as usual from the fact that it is equivalent to checking satisfiability of ¬ φ \neg\varphi ¬ φ .
Remark 3.13 (Adding converse). The above decidability proof can be easily extended to NPDL with converse programs π ⌣ \pi^{\smile} π ⌣ interpreted as R π ⌣ ( x , y ) = R π ( y , x ) R_{\pi^{\smile}}(x,y)=R_{\pi}(y,x) R π ⌣ ( x , y ) = R π ( y , x ) , as it is straightforward to verify the validities φ → [ π ] m ⟨ π ⌣ ⟩ m φ \varphi\to[\pi]^{m}\langle\pi^{\smile}\rangle^{m}\varphi φ → [ π ] m ⟨ π ⌣ ⟩ m φ and φ → [ π ⌣ ] m ⟨ π ⟩ m φ \varphi\to[\pi^{\smile}]^{m}\langle\pi\rangle^{m}\varphi φ → [ π ⌣ ] m ⟨ π ⟩ m φ and program equivalences ( π 1 ∪ π 2 ) ⌣ ≅ π 1 ⌣ ∪ π 2 ⌣ (\pi_{1}\cup\pi_{2})^{\smile}\cong\pi_{1}^{\smile}\cup\pi_{2}^{\smile} ( π 1 ∪ π 2 ) ⌣ ≅ π 1 ⌣ ∪ π 2 ⌣ , ( π 1 ; π 2 ) ⌣ ≅ π 2 ⌣ ; π 1 ⌣ (\pi_{1};\pi_{2})^{\smile}\cong\pi_{2}^{\smile};\pi_{1}^{\smile} ( π 1 ; π 2 ) ⌣ ≅ π 2 ⌣ ; π 1 ⌣ , and ( ψ ? ) ⌣ ≅ ψ ? (\psi?)^{\smile}\cong\psi? ( ψ ? ) ⌣ ≅ ψ ? analogous to standard PDL.
Completeness
In this section, we use the filtration technique developed in the previous section to obtain (weak) completeness via finite canonical models . The axioms of NPDL are as follows.
Definition 4.1 (⊢ N P D L \vdash_{\mathrm{NPDL}} ⊢ NPDL ). A formula φ \varphi φ is provable , denoted by ⊢ N P D L φ \vdash_{\mathrm{NPDL}}\varphi ⊢ NPDL φ , if it can be obtained from the following axioms together with propositional reasoning, modus ponens and the monotonicity rule φ → ψ ▹ ⟨ π ⟩ m φ → ⟨ π ⟩ m ψ \varphi\to\psi\ \triangleright\ \langle\pi\rangle^{m}\varphi\to\langle\pi\rangle^{m}\psi φ → ψ ▹ ⟨ π ⟩ m φ → ⟨ π ⟩ m ψ for every m ∈ N m\in\mathbb{N} m ∈ N :
⟨ π ⟩ m ⊥ ↔ ⊥ \langle\pi\rangle^{m}\bot\leftrightarrow\bot ⟨ π ⟩ m ⊥ ↔ ⊥
⟨ π ⟩ m ( φ ∨ ψ ) ↔ ⟨ π ⟩ m φ ∨ ⟨ π ⟩ m ψ \langle\pi\rangle^{m}(\varphi\lor\psi)\leftrightarrow\langle\pi\rangle^{m}\varphi\lor\langle\pi\rangle^{m}\psi ⟨ π ⟩ m ( φ ∨ ψ ) ↔ ⟨ π ⟩ m φ ∨ ⟨ π ⟩ m ψ
⟨ π ⟩ n φ → ⟨ π ⟩ m φ \langle\pi\rangle^{n}\varphi\to\langle\pi\rangle^{m}\varphi ⟨ π ⟩ n φ → ⟨ π ⟩ m φ for all n ≤ m n\le m n ≤ m
⟨ π 1 ∪ π 1 ⟩ m φ ↔ ⟨ π 1 ⟩ m φ ∨ ⟨ π 2 ⟩ m φ \langle\pi_{1}\cup\pi_{1}\rangle^{m}\varphi\leftrightarrow\langle\pi_{1}\rangle^{m}\varphi\lor\langle\pi_{2}\rangle^{m}\varphi ⟨ π 1 ∪ π 1 ⟩ m φ ↔ ⟨ π 1 ⟩ m φ ∨ ⟨ π 2 ⟩ m φ
⟨ π 1 ; π 2 ⟩ m φ ↔ ⋁ i = 0 m ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i φ \langle\pi_{1};\pi_{2}\rangle^{m}\varphi\leftrightarrow\bigvee_{i=0}^{m}\langle\pi_{1}\rangle^{i}\langle\pi_{2}\rangle^{m-i}\varphi ⟨ π 1 ; π 2 ⟩ m φ ↔ ⋁ i = 0 m ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i φ
⟨ π ∗ ⟩ m φ ↔ ⋁ i = 0 m ⟨ π ⟩ i φ \langle\pi^{*}\rangle^{m}\varphi\leftrightarrow\bigvee_{i=0}^{m}\langle\pi\rangle^{i}\varphi ⟨ π ∗ ⟩ m φ ↔ ⋁ i = 0 m ⟨ π ⟩ i φ
⟨ ψ ? ⟩ m φ ↔ ψ ∧ φ \langle\psi?\rangle^{m}\varphi\leftrightarrow\psi\land\varphi ⟨ ψ ? ⟩ m φ ↔ ψ ∧ φ
( φ ∧ ⋀ i = 0 m [ π ∗ ] i ( φ → [ π ] m − i φ ) ) → [ π ∗ ] m φ (\varphi\land\bigwedge_{i=0}^{m}[\pi^{*}]^{i}(\varphi\to[\pi]^{m-i}\varphi))\to[\pi^{*}]^{m}\varphi ( φ ∧ ⋀ i = 0 m [ π ∗ ] i ( φ → [ π ] m − i φ )) → [ π ∗ ] m φ
Soundness of (1)–(7) was shown in Proposition 2.11, we proceed to verify soundness of the induction rules (8). Let M = ⟨ X , { R a } a ∈ Π 0 , Val ⟩ \mathcal{M}=\langle X,\{R_{a}\}_{a\in\Pi_{0}},\operatorname{Val}\rangle M = ⟨ X , { R a } a ∈ Π 0 , Val ⟩ be a model and x ∈ X x\in X x ∈ X such that M , x ⊩ φ ∧ ⋀ i = 0 m [ π ∗ ] i ( φ → [ π ] m − i φ ) \mathcal{M},x\Vdash\varphi\land\bigwedge_{i=0}^{m}[\pi^{*}]^{i}(\varphi\to[\pi]^{m-i}\varphi) M , x ⊩ φ ∧ ⋀ i = 0 m [ π ∗ ] i ( φ → [ π ] m − i φ ) . To show M , x ⊩ [ π ∗ ] m φ \mathcal{M},x\Vdash[\pi^{*}]^{m}\varphi M , x ⊩ [ π ∗ ] m φ we inductively show
R π [ k ] ( x , y ) ≤ m ⇒ M , y ⊩ φ R_{\pi}^{[k]}(x,y)\le m\Rightarrow\mathcal{M},y\Vdash\varphi R π [ k ] ( x , y ) ≤ m ⇒ M , y ⊩ φ
for all k k k . The case k = 0 k=0 k = 0 follows from M , x ⊩ φ \mathcal{M},x\Vdash\varphi M , x ⊩ φ . For the inductive step k ↦ k + 1 k\mapsto k+1 k ↦ k + 1 suppose R π [ k + 1 ] ( x , y ) ≤ m R_{\pi}^{[k+1]}(x,y)\le m R π [ k + 1 ] ( x , y ) ≤ m . Then there exist v ∈ X v\in X v ∈ X such that R π [ k + 1 ] ( x , y ) = R π [ k ] ( x , v ) + R π ( v , y ) R_{\pi}^{[k+1]}(x,y)=R_{\pi}^{[k]}(x,v)+R_{\pi}(v,y) R π [ k + 1 ] ( x , y ) = R π [ k ] ( x , v ) + R π ( v , y ) . Set i : = R π [ k ] ( x , v ) i:=R_{\pi}^{[k]}(x,v) i := R π [ k ] ( x , v ) . Now we have M , v ⊩ φ \mathcal{M},v\Vdash\varphi M , v ⊩ φ by inductive hypothesis (note i ≤ m i\le m i ≤ m ) and M , v ⊩ φ → [ π ] m − i φ \mathcal{M},v\Vdash\varphi\to[\pi]^{m-i}\varphi M , v ⊩ φ → [ π ] m − i φ by the initial assumption. Thus we have M , v ⊩ [ π ] m − i φ \mathcal{M},v\Vdash[\pi]^{m-i}\varphi M , v ⊩ [ π ] m − i φ and since R π ( v , y ) ≤ m − i R_{\pi}(v,y)\le m-i R π ( v , y ) ≤ m − i we obtain M , y ⊩ φ \mathcal{M},y\Vdash\varphi M , y ⊩ φ as desired.
We now define the canonical pseudo-model based on the maximally consistent sets (‘pseudo’ indicates that it is not a model in the sense of Definition 2.7). As usual we say that a set of formulas Γ \Gamma Γ is consistent if there are no formulas φ 1 , … , φ ℓ ∈ Γ \varphi_{1},\ldots,\varphi_{\ell}\in\Gamma φ 1 , … , φ ℓ ∈ Γ such that ⊢ N P D L ⋀ i = 1 ℓ φ i → ⊥ \vdash_{\mathrm{NPDL}}\bigwedge_{i=1}^{\ell}\varphi_{i}\to\bot ⊢ NPDL ⋀ i = 1 ℓ φ i → ⊥ and maximally consistent if Γ ⊆ Γ ′ \Gamma\subseteq\Gamma' Γ ⊆ Γ ′ implies Γ = Γ ′ \Gamma=\Gamma' Γ = Γ ′ for every other consistent set Γ ′ \Gamma' Γ ′ .
Definition 4.2 (Canonical pseudo-model). We define the NPDL-canonical pseudo-model M c = ⟨ X c , { R π c } π ∈ Π , Val c ⟩ \mathcal{M}^{c}=\langle X^{c},\{R_{\pi}^{c}\}_{\pi\in\Pi},\operatorname{Val}^{c}\rangle M c = ⟨ X c , { R π c } π ∈ Π , Val c ⟩ as follows (note: we define R π c R_{\pi}^{c} R π c for all programs ).
X c X^{c} X c is the collection of all maximally NPDL-consistent sets,
R π c ( Γ , Γ ′ ) = { m ∈ N ∣ ∀ φ : φ ∈ Γ ′ ⇒ ⟨ π ⟩ m φ ∈ Γ } R_{\pi}^{c}(\Gamma,\Gamma')=\{m\in\mathbb{N}\mid\forall\varphi:\varphi\in\Gamma'\Rightarrow\langle\pi\rangle^{m}\varphi\in\Gamma\} R π c ( Γ , Γ ′ ) = { m ∈ N ∣ ∀ φ : φ ∈ Γ ′ ⇒ ⟨ π ⟩ m φ ∈ Γ } ,
Val c ( p ) = { Γ ∈ X c ∣ p ∈ Γ } \operatorname{Val}^{c}(p)=\{\Gamma\in X^{c}\mid p\in\Gamma\} Val c ( p ) = { Γ ∈ X c ∣ p ∈ Γ }
Similarly to the non-dynamic case [15 Lemma 4.2] , first we observe that ‘truth is membership ’ in the canonical pseudo-model.
Lemma 4.3 (Truth Lemma). For all formulas φ \varphi φ , it holds that M c , Γ ⊩ φ ⇔ φ ∈ Γ \mathcal{M}^{c},\Gamma\Vdash\varphi\Leftrightarrow\varphi\in\Gamma M c , Γ ⊩ φ ⇔ φ ∈ Γ .
Proof. Induction on the formula, the case of propositional variables is immediate by definition and the cases for propositional connectives are straightforward, so we consider the remaining case ⟨ π ⟩ m φ \langle\pi\rangle_m\varphi ⟨ π ⟩ m φ below.
If M c , Γ ⊩ ⟨ π ⟩ m φ \mathcal{M}^{c},\Gamma\Vdash\langle\pi\rangle_m\varphi M c , Γ ⊩ ⟨ π ⟩ m φ then there exists Γ ′ ∈ X c \Gamma'\in X^{c} Γ ′ ∈ X c with M c , Γ ′ ⊩ φ \mathcal{M}^{c},\Gamma'\Vdash\varphi M c , Γ ′ ⊩ φ and R π c ( Γ , Γ ′ ) ≤ m R_{\pi}^{c}(\Gamma,\Gamma')\leq m R π c ( Γ , Γ ′ ) ≤ m . The former together with the inductive hypothesis yields φ ∈ Γ ′ \varphi\in\Gamma' φ ∈ Γ ′ , which together with the latter implies ⟨ π ⟩ m φ \langle\pi\rangle_m\varphi ⟨ π ⟩ m φ as desired (note that here we use the axiom ⟨ π ⟩ n φ → ⟨ π ⟩ m φ \langle\pi\rangle_n\varphi\to\langle\pi\rangle_m\varphi ⟨ π ⟩ n φ → ⟨ π ⟩ m φ with n = R π c ( Γ , Γ ′ ) n=R_{\pi}^{c}(\Gamma,\Gamma') n = R π c ( Γ , Γ ′ ) ).
Conversely, assume that ⟨ π ⟩ m φ ∈ Γ \langle\pi\rangle_m\varphi\in\Gamma ⟨ π ⟩ m φ ∈ Γ , we want to construct a maximally consistent theory Γ ′ \Gamma' Γ ′ with φ ∈ Γ ′ \varphi\in\Gamma' φ ∈ Γ ′ and R π c ( Γ , Γ ′ ) ≤ m R_{\pi}^{c}(\Gamma,\Gamma')\leq m R π c ( Γ , Γ ′ ) ≤ m . For this, it suffices to show that the set
{ φ } ∪ { ψ ∣ [ π ] m ψ ∈ Γ } \{\varphi\}\cup\{\psi\mid[\pi]_m\psi\in\Gamma\} { φ } ∪ { ψ ∣ [ π ] m ψ ∈ Γ }
is consistent. Suppose towards contradiction that it is not consistent, then there are [ π ] m ψ 1 , … , [ π ] m ψ ℓ ∈ Γ [\pi]_m\psi_1,\ldots,[\pi]_m\psi_\ell\in\Gamma [ π ] m ψ 1 , … , [ π ] m ψ ℓ ∈ Γ such that ⊢ N P D L ψ 1 ∧ ⋯ ∧ ψ ℓ → ¬ φ \vdash_{\mathrm{NPDL}}\psi_1\land\cdots\land\psi_\ell\to\neg\varphi ⊢ NPDL ψ 1 ∧ ⋯ ∧ ψ ℓ → ¬ φ . The monotonicity rule yields
⊢ N P D L [ π ] m ψ 1 ∧ ⋯ ∧ [ π ] m ψ ℓ → ¬ ⟨ π ⟩ m φ . \vdash_{\mathrm{NPDL}}[\pi]_m\psi_1\land\cdots\land[\pi]_m\psi_\ell\to\neg\langle\pi\rangle_m\varphi. ⊢ NPDL [ π ] m ψ 1 ∧ ⋯ ∧ [ π ] m ψ ℓ → ¬ ⟨ π ⟩ m φ .
By construction we have that all [ π ] m ψ j ∈ Γ [\pi]_m\psi_j\in\Gamma [ π ] m ψ j ∈ Γ , therefore by the above ¬ ⟨ π ⟩ m φ \neg\langle\pi\rangle_m\varphi ¬ ⟨ π ⟩ m φ , a contradiction to our assumption that ⟨ π ⟩ m φ ∈ Γ \langle\pi\rangle_m\varphi\in\Gamma ⟨ π ⟩ m φ ∈ Γ and Γ \Gamma Γ is consistent. □
The following shows that the canonical pseudo-model is ‘well-behaved’ with respect to all program constructs except iteration.
Proposition 4.4. The following hold in the canonical pseudo-model:
( 1 ) R π 1 ∪ π 2 c = R π 1 c ∧ R π 2 c , ( 2 ) R π 1 ; π 2 c = R π 1 c ∘ R π 2 c , ( 3 ) R ψ ? c = Δ ⟦ ψ ⟧ . \begin{aligned}
(1)\quad R_{\pi_1\cup\pi_2}^{c}&=R_{\pi_1}^{c}\land R_{\pi_2}^{c},\\
(2)\quad R_{\pi_1;\pi_2}^{c}&=R_{\pi_1}^{c}\circ R_{\pi_2}^{c},\\
(3)\quad R_{\psi?}^{c}&=\Delta_{\llbracket\psi\rrbracket}.
\end{aligned} ( 1 ) R π 1 ∪ π 2 c ( 2 ) R π 1 ; π 2 c ( 3 ) R ψ ? c = R π 1 c ∧ R π 2 c , = R π 1 c ∘ R π 2 c , = Δ [ [ ψ ] ] .
Proof. (1): R π 1 c ( Γ , Γ ′ ) ∧ R π 2 c ( Γ , Γ ′ ) ≥ R π 1 ∪ π 2 c ( Γ , Γ ′ ) R_{\pi_1}^{c}(\Gamma,\Gamma')\land R_{\pi_2}^{c}(\Gamma,\Gamma')\geq R_{\pi_1\cup\pi_2}^{c}(\Gamma,\Gamma') R π 1 c ( Γ , Γ ′ ) ∧ R π 2 c ( Γ , Γ ′ ) ≥ R π 1 ∪ π 2 c ( Γ , Γ ′ ) is clear by definition (and the reduction axiom for ∪ \cup ∪ ). For the converse, suppose towards contradiction that R π 1 c ( Γ , Γ ′ ) ∧ R π 2 c ( Γ , Γ ′ ) > R π 1 ∪ π 2 c ( Γ , Γ ′ ) = : m R_{\pi_1}^{c}(\Gamma,\Gamma')\land R_{\pi_2}^{c}(\Gamma,\Gamma')>R_{\pi_1\cup\pi_2}^{c}(\Gamma,\Gamma')=:m R π 1 c ( Γ , Γ ′ ) ∧ R π 2 c ( Γ , Γ ′ ) > R π 1 ∪ π 2 c ( Γ , Γ ′ ) =: m . Then there are [ π 1 ] m φ , [ π 2 ] m ψ ∈ Γ [\pi_1]_m\varphi,[\pi_2]_m\psi\in\Gamma [ π 1 ] m φ , [ π 2 ] m ψ ∈ Γ such that φ , ψ ∉ Γ ′ \varphi,\psi\notin\Gamma' φ , ψ ∈ / Γ ′ . However, we have [ π 1 ∪ π 2 ] m ( φ ∨ ψ ) ∈ Γ [\pi_1\cup\pi_2]_m(\varphi\lor\psi)\in\Gamma [ π 1 ∪ π 2 ] m ( φ ∨ ψ ) ∈ Γ and thus φ ∨ ψ ∈ Γ ′ \varphi\lor\psi\in\Gamma' φ ∨ ψ ∈ Γ ′ , contradicting maximality of Γ ′ \Gamma' Γ ′ .
(2): We want to show that R π 1 ; π 2 c ( Γ , Γ ′ ) = ⋀ Δ ∈ X c R π 1 c ( Γ , Δ ) + R π 2 c ( Δ , Γ ′ ) R_{\pi_1;\pi_2}^{c}(\Gamma,\Gamma')=\bigwedge_{\Delta\in X^{c}}R_{\pi_1}^{c}(\Gamma,\Delta)+R_{\pi_2}^{c}(\Delta,\Gamma') R π 1 ; π 2 c ( Γ , Γ ′ ) = ⋀ Δ ∈ X c R π 1 c ( Γ , Δ ) + R π 2 c ( Δ , Γ ′ ) . To see ‘≤ \leq ≤ ’ suppose the right hand side is given by m : = R π 1 c ( Γ , Δ ) + R π 2 c ( Δ , Γ ′ ) m:=R_{\pi_1}^{c}(\Gamma,\Delta)+R_{\pi_2}^{c}(\Delta,\Gamma') m := R π 1 c ( Γ , Δ ) + R π 2 c ( Δ , Γ ′ ) . Let i : = R π 1 c ( Γ , Δ ) i:=R_{\pi_1}^{c}(\Gamma,\Delta) i := R π 1 c ( Γ , Δ ) . Now R π 1 ; π 2 c ( Γ , Γ ′ ) ≤ m R_{\pi_1;\pi_2}^{c}(\Gamma,\Gamma')\leq m R π 1 ; π 2 c ( Γ , Γ ′ ) ≤ m holds since for all formulas φ \varphi φ we have
φ ∈ Γ ′ ⇒ ⟨ π 2 ⟩ m − i φ ∈ Δ ⇒ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i φ ∈ Γ ⇒ ⟨ π 1 ; π 2 ⟩ m φ ∈ Γ . \varphi\in\Gamma'\Rightarrow\langle\pi_2\rangle_{m-i}\varphi\in\Delta\Rightarrow\langle\pi_1\rangle_i\langle\pi_2\rangle_{m-i}\varphi\in\Gamma\Rightarrow\langle\pi_1;\pi_2\rangle_m\varphi\in\Gamma. φ ∈ Γ ′ ⇒ ⟨ π 2 ⟩ m − i φ ∈ Δ ⇒ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i φ ∈ Γ ⇒ ⟨ π 1 ; π 2 ⟩ m φ ∈ Γ.
For the opposite inequality ‘≥ \geq ≥ ’, now let R π 1 ; π 2 c ( Γ , Γ ′ ) = m R_{\pi_1;\pi_2}^{c}(\Gamma,\Gamma')=m R π 1 ; π 2 c ( Γ , Γ ′ ) = m . Note that it suffices to show that there exists some i ∈ { 0 , … , m } i\in\{0,\ldots,m\} i ∈ { 0 , … , m } such that the following set of formulas is consistent:
Δ i = { φ ∣ [ π 1 ] i φ ∈ Γ } ∪ { ⟨ π 2 ⟩ m − i ψ ∣ ψ ∈ Γ ′ } . \Delta^{i}=\{\varphi\mid[\pi_1]_{i}\varphi\in\Gamma\}\cup\{\langle\pi_2\rangle_{m-i}\psi\mid\psi\in\Gamma'\}. Δ i = { φ ∣ [ π 1 ] i φ ∈ Γ } ∪ {⟨ π 2 ⟩ m − i ψ ∣ ψ ∈ Γ ′ } .
Suppose towards contradiction that all Δ i \Delta^{i} Δ i are inconsistent. Then for each i i i we there are [ π 1 ] i φ 1 i , … , [ π 1 ] i φ k i i ∈ Γ [\pi_1]_{i}\varphi^{i}_{1},\ldots,[\pi_1]_{i}\varphi^{i}_{k_i}\in\Gamma [ π 1 ] i φ 1 i , … , [ π 1 ] i φ k i i ∈ Γ and ψ 1 i , … , ψ ℓ i i ∈ Γ ′ \psi^{i}_{1},\ldots,\psi^{i}_{\ell_i}\in\Gamma' ψ 1 i , … , ψ ℓ i i ∈ Γ ′ such that
⊢ N P D L φ 1 i ∧ ⋯ ∧ φ k i i ∧ ⟨ π 2 ⟩ m − i ψ 1 i ∧ ⋯ ∧ ⟨ π 2 ⟩ m − i ψ ℓ i i → ⊥ . \vdash_{\mathrm{NPDL}}\varphi^{i}_{1}\land\cdots\land\varphi^{i}_{k_i}\land\langle\pi_2\rangle_{m-i}\psi^{i}_{1}\land\cdots\land\langle\pi_2\rangle_{m-i}\psi^{i}_{\ell_i}\to\bot. ⊢ NPDL φ 1 i ∧ ⋯ ∧ φ k i i ∧ ⟨ π 2 ⟩ m − i ψ 1 i ∧ ⋯ ∧ ⟨ π 2 ⟩ m − i ψ ℓ i i → ⊥.
Set Φ i = ⋀ { φ j i ∣ 1 ≤ j ≤ k i } \Phi^{i}=\bigwedge\{\varphi^{i}_{j}\mid1\leq j\leq k_i\} Φ i = ⋀ { φ j i ∣ 1 ≤ j ≤ k i } and Ψ i = ⋀ { ψ j i ∣ 1 ≤ j ≤ ℓ i } \Psi^{i}=\bigwedge\{\psi^{i}_{j}\mid1\leq j\leq\ell_i\} Ψ i = ⋀ { ψ j i ∣ 1 ≤ j ≤ ℓ i } . With this and the fact that ⊢ N P D L ⟨ π 2 ⟩ m − i ( p ∧ q ) → ⟨ π 2 ⟩ m − i p ∧ ⟨ π 2 ⟩ m − i q \vdash_{\mathrm{NPDL}}\langle\pi_2\rangle_{m-i}(p\land q)\to\langle\pi_2\rangle_{m-i}p\land\langle\pi_2\rangle_{m-i}q ⊢ NPDL ⟨ π 2 ⟩ m − i ( p ∧ q ) → ⟨ π 2 ⟩ m − i p ∧ ⟨ π 2 ⟩ m − i q the above implies ⊢ N P D L Φ i → ¬ ⟨ π 2 ⟩ m − i Ψ i \vdash_{\mathrm{NPDL}}\Phi^{i}\to\neg\langle\pi_2\rangle_{m-i}\Psi^{i} ⊢ NPDL Φ i → ¬ ⟨ π 2 ⟩ m − i Ψ i , thus by monotonicity of [ π 1 ] i [\pi_1]^{i} [ π 1 ] i we find
⊢ N P D L [ π 1 ] i Φ i → ¬ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ i . \vdash_{\mathrm{NPDL}}[\pi_1]^{i}\Phi^{i}\to\neg\langle\pi_1\rangle^{i}\langle\pi_2\rangle_{m-i}\Psi^{i}. ⊢ NPDL [ π 1 ] i Φ i → ¬ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ i .
Now let Ψ = ⋀ { Ψ i ∣ 0 ≤ i ≤ m } \Psi=\bigwedge\{\Psi^{i}\mid0\leq i\leq m\} Ψ = ⋀ { Ψ i ∣ 0 ≤ i ≤ m } . Since Ψ → Ψ i \Psi\to\Psi^{i} Ψ → Ψ i the above also yields
⊢ N P D L [ π 1 ] i Φ i → ¬ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ . \vdash_{\mathrm{NPDL}}[\pi_1]^{i}\Phi^{i}\to\neg\langle\pi_1\rangle^{i}\langle\pi_2\rangle_{m-i}\Psi. ⊢ NPDL [ π 1 ] i Φ i → ¬ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ.
Now, on the one hand, observe that Ψ ∈ Γ ′ \Psi\in\Gamma' Ψ ∈ Γ ′ and therefore it holds that ⟨ π 1 ; π 2 ⟩ m Ψ ∈ Γ \langle\pi_1;\pi_2\rangle_m\Psi\in\Gamma ⟨ π 1 ; π 2 ⟩ m Ψ ∈ Γ (since R π 1 ; π 2 c ( Γ , Γ ′ ) = m R_{\pi_1;\pi_2}^{c}(\Gamma,\Gamma')=m R π 1 ; π 2 c ( Γ , Γ ′ ) = m ). Due to our axioms, we get ⋁ i = 0 m ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ ∈ Γ \bigvee_{i=0}^{m}\langle\pi_1\rangle^{i}\langle\pi_2\rangle_{m-i}\Psi\in\Gamma ⋁ i = 0 m ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ ∈ Γ and therefore ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − 1 Ψ ∈ Γ \langle\pi_1\rangle^{i}\langle\pi_2\rangle^{m-1}\Psi\in\Gamma ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − 1 Ψ ∈ Γ must hold for some i i i . On the other hand, however, since by definition ⟨ π 1 ⟩ i Φ i ∈ Γ \langle\pi_1\rangle^{i}\Phi_i \in\Gamma ⟨ π 1 ⟩ i Φ i ∈ Γ , the above derivation implies ¬ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ ∈ Γ \neg\langle\pi_1\rangle^{i}\langle\pi_2\rangle^{m-i}\Psi\in\Gamma ¬ ⟨ π 1 ⟩ i ⟨ π 2 ⟩ m − i Ψ ∈ Γ , a contradiction.
(3): Note that ⟨ ψ ? ⟩ φ m φ ∈ Γ \langle\psi?\rangle^{m}_{\varphi}\varphi\in\Gamma ⟨ ψ ? ⟩ φ m φ ∈ Γ if and only if ⟨ ψ ? ⟩ φ 0 φ ∈ Γ \langle\psi?\rangle^{0}_{\varphi}\varphi\in\Gamma ⟨ ψ ? ⟩ φ 0 φ ∈ Γ due to our reduction axioms for tests. Therefore either R ψ ? c ( Γ , Γ ′ ) = ∞ R^{c}_{\psi?}(\Gamma,\Gamma')=\infty R ψ ? c ( Γ , Γ ′ ) = ∞ or R ψ ? c ( Γ , Γ ′ ) = 0 R^{c}_{\psi?}(\Gamma,\Gamma')=0 R ψ ? c ( Γ , Γ ′ ) = 0 . The latter holds if and only if ∀ φ : φ ∈ Γ ′ ⇒ ψ ∧ φ ∈ Γ \forall\varphi:\varphi\in\Gamma' \Rightarrow\psi\land\varphi\in\Gamma ∀ φ : φ ∈ Γ ′ ⇒ ψ ∧ φ ∈ Γ which is equivalent to Γ ′ = Γ \Gamma'=\Gamma Γ ′ = Γ (by maximality and Γ ′ ⊆ Γ \Gamma'\subseteq\Gamma Γ ′ ⊆ Γ ) and M c , Γ ⊩ ψ \mathcal{M}^{c},\Gamma\Vdash\psi M c , Γ ⊩ ψ (by the Lemma 4.3 and ψ ∈ Γ \psi\in\Gamma ψ ∈ Γ ). □
While the canonical pseudo-model does not satisfy R π ∗ c = ( R π c ) ∗ R^{c}_{\pi^*}=(R^{c}_{\pi})^* R π ∗ c = ( R π c ) ∗ , it still retains some similar properties, as shown in the following.
Lemma 4.5. For every program π \pi π , the canonical pseudo-model satisfies:
(1) R π ∗ c ( Γ , Γ ) = 0 R^{c}_{\pi^*}(\Gamma,\Gamma)=0 R π ∗ c ( Γ , Γ ) = 0 ,
(2) R π c ( Γ , Γ ′ ) ≥ R π ∗ c ( Γ , Γ ′ ) R^{c}_{\pi}(\Gamma,\Gamma')\ge R^{c}_{\pi^*}(\Gamma,\Gamma') R π c ( Γ , Γ ′ ) ≥ R π ∗ c ( Γ , Γ ′ ) ,
(3) R π ∗ c ( Γ , Δ ) + R π ∗ c ( Δ , Γ ′ ) ≥ R π ∗ c ( Γ , Γ ′ ) R^{c}_{\pi^*}(\Gamma,\Delta)+R^{c}_{\pi^*}(\Delta,\Gamma')\ge R^{c}_{\pi^*}(\Gamma,\Gamma') R π ∗ c ( Γ , Δ ) + R π ∗ c ( Δ , Γ ′ ) ≥ R π ∗ c ( Γ , Γ ′ ) .
Proof. (1): If φ ∈ Γ \varphi\in\Gamma φ ∈ Γ , then also ⟨ π ∗ ⟩ 0 φ ∈ Γ \langle\pi^*\rangle^0\varphi\in\Gamma ⟨ π ∗ ⟩ 0 φ ∈ Γ since ⊢ N P D L φ → ⟨ π ∗ ⟩ 0 φ \vdash_{\mathrm{NPDL}}\varphi\to\langle\pi^*\rangle^0\varphi ⊢ NPDL φ → ⟨ π ∗ ⟩ 0 φ .
(2): Let R π ∗ c ( Γ , Γ ′ ) = m R^{c}_{\pi^*}(\Gamma,\Gamma')=m R π ∗ c ( Γ , Γ ′ ) = m . If φ ∈ Γ ′ \varphi\in\Gamma' φ ∈ Γ ′ , then ⟨ π ⟩ m φ ∈ Γ \langle\pi\rangle^m\varphi\in\Gamma ⟨ π ⟩ m φ ∈ Γ , since the monotonicity rule yields ⊢ N P D L ⟨ π ⟩ m φ → ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 φ \vdash_{\mathrm{NPDL}}\langle\pi\rangle^m\varphi\to\langle\pi\rangle^m\langle\pi^*\rangle^0\varphi ⊢ NPDL ⟨ π ⟩ m φ → ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 φ we find ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 φ ∈ Γ \langle\pi\rangle^m\langle\pi^*\rangle^0\varphi\in\Gamma ⟨ π ⟩ m ⟨ π ∗ ⟩ 0 φ ∈ Γ , which lastly yields ⟨ π ∗ ⟩ m φ ∈ Γ \langle\pi^*\rangle^m\varphi\in\Gamma ⟨ π ∗ ⟩ m φ ∈ Γ , showing R π ∗ c ( Γ , Γ ′ ) ≤ m R^{c}_{\pi^*}(\Gamma,\Gamma')\le m R π ∗ c ( Γ , Γ ′ ) ≤ m as desired.
(3): Let R π ∗ c ( Γ , Δ ) = i R^{c}_{\pi^*}(\Gamma,\Delta)=i R π ∗ c ( Γ , Δ ) = i and R π ∗ c ( Δ , Γ ′ ) = m − i R^{c}_{\pi^*}(\Delta,\Gamma')=m-i R π ∗ c ( Δ , Γ ′ ) = m − i . If φ ∈ Γ ′ \varphi\in\Gamma' φ ∈ Γ ′ then ⟨ π ∗ ⟩ m − i φ ∈ Δ \langle\pi^*\rangle^{m-i}\varphi\in\Delta ⟨ π ∗ ⟩ m − i φ ∈ Δ and therefore ⟨ π ∗ ⟩ i ⟨ π ∗ ⟩ m − i φ ∈ Γ \langle\pi^*\rangle^{i}\langle\pi^*\rangle^{m-i}\varphi\in\Gamma ⟨ π ∗ ⟩ i ⟨ π ∗ ⟩ m − i φ ∈ Γ . Due to ⊢ N P D L ⟨ π ∗ ⟩ i ⟨ π ∗ ⟩ m − i φ → ⟨ π ∗ ⟩ m φ \vdash_{\mathrm{NPDL}}\langle\pi^*\rangle^{i}\langle\pi^*\rangle^{m-i}\varphi\to\langle\pi^*\rangle^{m}\varphi ⊢ NPDL ⟨ π ∗ ⟩ i ⟨ π ∗ ⟩ m − i φ → ⟨ π ∗ ⟩ m φ we get ⟨ π ∗ ⟩ m φ ∈ Γ \langle\pi^*\rangle^{m}\varphi\in\Gamma ⟨ π ∗ ⟩ m φ ∈ Γ as well, showing R π ∗ c ( Γ , Γ ′ ) ≤ m R^{c}_{\pi^*}(\Gamma,\Gamma')\le m R π ∗ c ( Γ , Γ ′ ) ≤ m as desired. □
Crucially, the Filtration Theorem (Theorem 3.7) still works for the canonical pseudo-model.
Theorem 4.6 (Filtration Theorem II). Let M φ f \mathcal{M}^{f}_{\varphi} M φ f be the filtration of the canonical pseudo-model M c \mathcal{M}^{c} M c as in Definition 3.6.
(i) For all formulas ψ \psi ψ with ψ ∈ F L ( φ ) \psi\in FL(\varphi) ψ ∈ F L ( φ ) : M c , x ⊩ ψ ⇔ M φ f , [ x ] ⊩ ψ \mathcal{M}^{c},x\Vdash\psi\Leftrightarrow\mathcal{M}^{f}_{\varphi},[x]\Vdash\psi M c , x ⊩ ψ ⇔ M φ f , [ x ] ⊩ ψ .
(ii) For all programs π \pi π with ⟨ π ⟩ m ψ ∈ F L ( φ ) \langle\pi\rangle^{m}\psi\in FL(\varphi) ⟨ π ⟩ m ψ ∈ F L ( φ ) :
(a) R π f ( [ x ] , [ y ] ) ≤ R π c ( x , y ) R^{f}_{\pi}([x],[y])\le R^{c}_{\pi}(x,y) R π f ([ x ] , [ y ]) ≤ R π c ( x , y ) ,
(b) If R π f ( [ x ] , [ y ] ) ≤ m R^{f}_{\pi}([x],[y])\le m R π f ([ x ] , [ y ]) ≤ m and M c , y ⊩ ψ \mathcal{M}^{c},y\Vdash\psi M c , y ⊩ ψ , then M c , x ⊩ ⟨ π ⟩ m ψ \mathcal{M}^{c},x\Vdash\langle\pi\rangle^{m}\psi M c , x ⊩ ⟨ π ⟩ m ψ .
Proof. The only part that is not completely analogous to the proof of Theorem 3.7 is to show that (a) holds for iteration. We show by induction that for all m ∈ N m\in\mathbb{N} m ∈ N
R π ∗ c ( x , y ) = m ⇒ R π ∗ f ( [ x ] , [ y ] ) ≤ m . R^{c}_{\pi^*}(x,y)=m \Rightarrow R^{f}_{\pi^*}([x],[y])\le m. R π ∗ c ( x , y ) = m ⇒ R π ∗ f ([ x ] , [ y ]) ≤ m . We begin with the case m = 0 m=0 m = 0 . Let R π ∗ c ( x , y ) = 0 R^{c}_{\pi^*}(x,y)=0 R π ∗ c ( x , y ) = 0 . Define
E = { z ∣ R π ∗ f ( [ x ] , [ z ] ) = 0 } E=\{z\mid R^{f}_{\pi^*}([x],[z])=0\} E = { z ∣ R π ∗ f ([ x ] , [ z ]) = 0 } and note that there exists a formula χ E \chi_E χ E such that M c , z ⊩ χ E ⇔ z ∈ E \mathcal{M}^{c},z\Vdash\chi_E\Leftrightarrow z\in E M c , z ⊩ χ E ⇔ z ∈ E since F L ( φ ) FL(\varphi) F L ( φ ) is finite. We want to show y ∈ E y\in E y ∈ E , for which it suffices to show that x ⊩ ⟨ π ∗ ⟩ 0 χ E x\Vdash\langle\pi^*\rangle^0\chi_E x ⊩ ⟨ π ∗ ⟩ 0 χ E . This we derive from the induction axiom for [ π ∗ ] 0 [\pi^*]^0 [ π ∗ ] 0 . We have x ⊩ χ E x\Vdash\chi_E x ⊩ χ E since R π ∗ f ( [ x ] , [ x ] ) = 0 R^{f}_{\pi^*}([x],[x])=0 R π ∗ f ([ x ] , [ x ]) = 0 . Now whenever R π ∗ c ( x , z ) = 0 R^{c}_{\pi^*}(x,z)=0 R π ∗ c ( x , z ) = 0 and z ⊩ χ E z\Vdash\chi_E z ⊩ χ E and R π c ( z , z ′ ) = 0 R^{c}_{\pi}(z,z')=0 R π c ( z , z ′ ) = 0 we have R π ∗ f ( [ x ] , [ z ′ ] ) ≤ R π ∗ f ( [ x ] , [ z ] ) + R π f ( [ z ] , [ z ′ ] ) = 0 R^{f}_{\pi^*}([x],[z'])\le R^{f}_{\pi^*}([x],[z])+R^{f}_{\pi}([z],[z'])=0 R π ∗ f ([ x ] , [ z ′ ]) ≤ R π ∗ f ([ x ] , [ z ]) + R π f ([ z ] , [ z ′ ]) = 0 (since z ⊩ χ E z\Vdash\chi_E z ⊩ χ E and inductive hypothesis on π \pi π ), thus z ′ ∈ E z'\in E z ′ ∈ E . So we showed x ⊩ χ E ∧ [ π ∗ ] 0 ( χ E → [ π ] 0 χ E ) x\Vdash\chi_E\land[\pi^*]^0(\chi_E\to[\pi]^0\chi_E) x ⊩ χ E ∧ [ π ∗ ] 0 ( χ E → [ π ] 0 χ E ) as needed.
Now inductively assume R π ∗ c ( u , v ) = n ⇒ R π ∗ f ( [ u ] , [ v ] ) ≤ n R^{c}_{\pi^*}(u,v)=n\Rightarrow R^{f}_{\pi^*}([u],[v])\le n R π ∗ c ( u , v ) = n ⇒ R π ∗ f ([ u ] , [ v ]) ≤ n holds for all n < m n<m n < m and let R π ∗ c ( [ x ] , [ y ] ) = m R^{c}_{\pi^*}([x],[y])=m R π ∗ c ([ x ] , [ y ]) = m . Similarly to before, define E = { z ∣ R π ∗ f ( [ x ] , [ z ] ) ≤ R π ∗ c ( x , z ) } E=\{z\mid R^{f}_{\pi^*}([x],[z])\le R^{c}_{\pi^*}(x,z)\} E = { z ∣ R π ∗ f ([ x ] , [ z ]) ≤ R π ∗ c ( x , z )} and let χ E \chi_E χ E be a formula defining this set. As before, we have x ⊩ χ E x\Vdash\chi_E x ⊩ χ E , so it suffices to show x ⊩ [ π ∗ ] i ( χ E → [ π ] m − i χ E ) x\Vdash[\pi^*]^i(\chi_E\to[\pi]^{m-i}\chi_E) x ⊩ [ π ∗ ] i ( χ E → [ π ] m − i χ E ) for all i = 0 , … , m i=0,\ldots,m i = 0 , … , m , since then the induction axiom for [ π ∗ ] m [\pi^*]^m [ π ∗ ] m yields x ⊩ [ π ∗ ] m χ E x\Vdash[\pi^*]^m\chi_E x ⊩ [ π ∗ ] m χ E and thus y ⊩ χ E y\Vdash\chi_E y ⊩ χ E as needed. Let R π ∗ c ( x , z ) ≤ i R^{c}_{\pi^*}(x,z)\le i R π ∗ c ( x , z ) ≤ i and z ⊩ χ E z\Vdash\chi_E z ⊩ χ E and R π ∗ c ( z , z ′ ) ≤ m − i R^{c}_{\pi^*}(z,z')\le m-i R π ∗ c ( z , z ′ ) ≤ m − i . Note that $R^{c}_{\pi^*}(x,z')\le
R π ∗ c ( x , z ) + R π ∗ c ( z , z ′ ) ≤ m R_{\pi^*}^{c}(x,z) + R_{\pi^*}^{c}(z,z') \leq m R π ∗ c ( x , z ) + R π ∗ c ( z , z ′ ) ≤ m . If R π ∗ c ( x , z ′ ) = n < m R_{\pi^*}^{c}(x,z') = n < m R π ∗ c ( x , z ′ ) = n < m , then the inductive hypothesis on n n n yields R π ∗ f ( [ x ] , [ z ′ ] ) ≤ n R_{\pi^*}^{f}([x],[z']) \leq n R π ∗ f ([ x ] , [ z ′ ]) ≤ n , showing z ′ ⊩ χ E z' \Vdash\chi_E z ′ ⊩ χ E . If R π ∗ c ( x , z ′ ) = m R_{\pi^*}^{c}(x,z') = m R π ∗ c ( x , z ′ ) = m then
R π ∗ f ( [ x ] , [ z ′ ] ) ≤ R π ∗ f ( [ x ] , [ z ] ) + R π ∗ f ( [ z ] , [ z ′ ] ) ≤ m R_{\pi^*}^{f}([x],[z']) \leq R_{\pi^*}^{f}([x],[z]) + R_{\pi^*}^{f}([z],[z']) \leq m R π ∗ f ([ x ] , [ z ′ ]) ≤ R π ∗ f ([ x ] , [ z ]) + R π ∗ f ([ z ] , [ z ′ ]) ≤ m
where we used z ⊩ χ E z \Vdash\chi_E z ⊩ χ E and the inductive hypothesis on π \pi π as R π ∗ f ( [ z ] , [ z ′ ] ) ≤ R π ∗ c ( z , z ′ ) R_{\pi^*}^{f}([z],[z']) \leq R_{\pi^*}^{c}(z,z') R π ∗ f ([ z ] , [ z ′ ]) ≤ R π ∗ c ( z , z ′ ) . This finishes the proof. □
Since M f \mathcal{M}^{f} M f is a (proper) model by definition, completeness is now a direct consequence.
Corollary 4.7 (Completeness). A formula is NPDL-valid if and only if it is ⊢ N P D L \vdash_{\mathrm{NPDL}} ⊢ NPDL -provable.
Proof. Soundness was discussed before, completeness is shown as follows. If ⊬ N P D L φ \nvdash_{\mathrm{NPDL}} \varphi ⊬ NPDL φ , then { ¬ φ } \{\neg\varphi\} { ¬ φ } is consistent, thus (by Lindenbaum’s Lemma) can be extended to a maximally consistent set Γ \Gamma Γ . By Lemma 4.3 and Theorem 4.6 we get that M φ , [ Γ ] f ⊮ φ \mathcal{M}^{f}_{\varphi,[\Gamma]} \not\Vdash\varphi M φ , [ Γ ] f ⊩ φ , showing that φ \varphi φ is not valid. □
Complexity Bounds
In this section, we obtain bounds on the complexity NPDL using translation between this logic and standard PDL. More specifically, we obtain a EXPTIME-lower bound via a translation σ \sigma σ of standard PDL into NPDL (Corollary 5.1) and we obtain a 2EXPTIME-upper bound via a translation of NPDL into standard PDL over an extended set of atomic programs (Corollary 5.6). We also give a complexity bound for the model checking problem of NPDL which significantly improves the bound obtained via the translation into PDL (Subsection 5.2).
Satisfiability Problem via Logical Translations
Translating standard PDL into NPDL is fairly straightforward, recalling that the weight 0 was taken to generalize standard accessibility. That is, for every formula φ \varphi φ of PDL we define a formula σ ( φ ) \sigma(\varphi) σ ( φ ) of NPDL inductively by the rules
σ ( p ) = p \sigma(p) = p σ ( p ) = p
σ ( ¬ φ ) = ¬ σ ( φ ) \sigma(\neg\varphi) = \neg\sigma(\varphi) σ ( ¬ φ ) = ¬ σ ( φ )
σ ( φ 1 ∧ φ 2 ) = σ ( φ 1 ) ∧ σ ( φ 2 ) \sigma(\varphi_1 \land\varphi_2) = \sigma(\varphi_1) \land\sigma(\varphi_2) σ ( φ 1 ∧ φ 2 ) = σ ( φ 1 ) ∧ σ ( φ 2 )
σ ( ⟨ π ⟩ φ ) = ⟨ π ⟩ 0 σ ( φ ) \sigma(\langle\pi\rangle\varphi) = \langle\pi\rangle^{0}\sigma(\varphi) σ (⟨ π ⟩ φ ) = ⟨ π ⟩ 0 σ ( φ )
Given a model M = ⟨ X , { R a } Π 0 , Val ⟩ \mathcal{M} = \langle X,\{R_a\}_{\Pi_0},\operatorname{Val}\rangle M = ⟨ X , { R a } Π 0 , Val ⟩ of PDL (i.e., R a ⊆ X 2 R_a \subseteq X^2 R a ⊆ X 2 are non-weighted atomic accessibility relations), we define a corresponding NPDL-model S ( M ) = ⟨ X , { R a ′ } Π 0 , Val ⟩ \mathcal{S}(\mathcal{M}) = \langle X,\{R'_a\}_{\Pi_0},\operatorname{Val}\rangle S ( M ) = ⟨ X , { R a ′ } Π 0 , Val ⟩ by
R a ′ ( x , y ) = { 0 if x R a y , ∞ otherwise. R'_a(x,y) =
\begin{cases}
0 & \text{if } xR_a y,\\
\infty& \text{otherwise.}
\end{cases} R a ′ ( x , y ) = { 0 ∞ if x R a y , otherwise.
By definition it is straightforward to check that the above extends to all programs π \pi π and that
M , x ⊩ φ if and only if S ( M ) , x ⊩ σ ( φ ) . \mathcal{M},x \Vdash\varphi\quad\text{if and only if}\quad\mathcal{S}(\mathcal{M}),x \Vdash\sigma(\varphi). M , x ⊩ φ if and only if S ( M ) , x ⊩ σ ( φ ) .
Since the translation σ \sigma σ does not increase the length of the formula φ \varphi φ , we obtain our lower bound from the fact that PDL is EXPTIME-complete (e.g. see [10 Chapter 8] ).
Corollary 5.1 (Lower Bound). Satisfiability of NPDL is EXPTIME-hard.
In order to obtain an upper bound as well, we now present a translation τ \tau τ of NPDL into standard PDL over the set of atomic programs
Π 0 = N : = { a = m ∣ a ∈ Π 0 , m ∈ N } . \Pi_0^{= \mathbb{N}} := \{a^{=m} \mid a \in\Pi_0, m \in\mathbb{N}\}. Π 0 = N := { a = m ∣ a ∈ Π 0 , m ∈ N } .
The idea is that the standard PDL program a = m a^{=m} a = m encodes the information R a ( x , y ) = m R_a(x,y)=m R a ( x , y ) = m in a model of NPDL. From this, one can recover complex NPDL program constructs as follows.
Definition 5.2 (Formula translation). By simultaneous induction, for all formulas φ \varphi φ and programs π \pi π of NPDL we define the formula τ ( φ ) \tau(\varphi) τ ( φ ) and for every m ∈ N m \in\mathbb{N} m ∈ N the program τ ≤ m ( φ ) \tau^{\leq m}(\varphi) τ ≤ m ( φ ) of PDL (over the set of atomic programs Π 0 N \Pi_0^{\mathbb{N}} Π 0 N as above) as follows.
Formulas:
τ ( p ) = p \tau(p) = p τ ( p ) = p for propositional variables
τ ( ¬ φ ) = ¬ τ ( φ ) \tau(\neg\varphi) = \neg\tau(\varphi) τ ( ¬ φ ) = ¬ τ ( φ )
τ ( φ 1 ∧ φ 2 ) = τ ( φ 1 ) ∧ τ ( φ 2 ) \tau(\varphi_1 \land\varphi_2) = \tau(\varphi_1) \land\tau(\varphi_2) τ ( φ 1 ∧ φ 2 ) = τ ( φ 1 ) ∧ τ ( φ 2 )
τ ( ⟨ π ⟩ m φ ) = ⟨ τ ≤ m ( π ) ⟩ τ ( φ ) \tau(\langle\pi\rangle^m\varphi) = \langle\tau^{\leq m}(\pi)\rangle\tau(\varphi) τ (⟨ π ⟩ m φ ) = ⟨ τ ≤ m ( π )⟩ τ ( φ )
Programs:
τ ≤ m ( a ) = ⋃ i = 0 m a = m \tau^{\leq m}(a) = \bigcup_{i=0}^{m} a^{=m} τ ≤ m ( a ) = ⋃ i = 0 m a = m for atomic programs
τ ≤ m ( π 1 ∪ π 2 ) = τ ≤ m ( π 1 ) ∪ τ ≤ m ( π 2 ) \tau^{\leq m}(\pi_1 \cup\pi_2) = \tau^{\leq m}(\pi_1) \cup\tau^{\leq m}(\pi_2) τ ≤ m ( π 1 ∪ π 2 ) = τ ≤ m ( π 1 ) ∪ τ ≤ m ( π 2 )
τ ≤ m ( π 1 ; π 2 ) = ⋃ i = 0 m τ ≤ i ( π 1 ) ; τ ≤ m − i ( π 2 ) \tau^{\leq m}(\pi_1;\pi_2) = \bigcup_{i=0}^{m}\tau^{\leq i}(\pi_1);\tau^{\leq m-i}(\pi_2) τ ≤ m ( π 1 ; π 2 ) = ⋃ i = 0 m τ ≤ i ( π 1 ) ; τ ≤ m − i ( π 2 )
τ ≤ 0 ( π ∗ ) = τ ≤ 0 ( π ∗ ) ∗ \tau^{\leq0}(\pi^*) = \tau^{\leq0}(\pi^*)^* τ ≤ 0 ( π ∗ ) = τ ≤ 0 ( π ∗ ) ∗ and τ ≤ m ( π ∗ ) = τ ≤ 0 ( π ∗ ) ∪ ⋃ i = 1 m τ ≤ 0 ( π ∗ ) ; τ ≤ i ( π ) ; τ ≤ m − i ( π ∗ ) \tau^{\leq m}(\pi^*) = \tau^{\leq0}(\pi^*) \cup\bigcup_{i=1}^{m}\tau^{\leq0}(\pi^*);\tau^{\leq i}(\pi);\tau^{\leq m-i}(\pi^*) τ ≤ m ( π ∗ ) = τ ≤ 0 ( π ∗ ) ∪ ⋃ i = 1 m τ ≤ 0 ( π ∗ ) ; τ ≤ i ( π ) ; τ ≤ m − i ( π ∗ )
τ ≤ m ( φ ? ) = τ ( φ ) ? \tau^{\leq m}(\varphi?) = \tau(\varphi)? τ ≤ m ( φ ?) = τ ( φ )?
As mentioned above, we now explain how to transform a model of NPDL into a model of PDL over the extended collection of atomic programs Π 0 N \Pi_0^{\mathbb{N}} Π 0 N .
Definition 5.3 (Model transformation). For M = ⟨ X , { R a } Π 0 , Val ⟩ \mathcal{M} = \langle X,\{R_a\}_{\Pi_0},\operatorname{Val}\rangle M = ⟨ X , { R a } Π 0 , Val ⟩ a NPDL-model, we define the PDL( Π 0 N ) (\Pi_0^{\mathbb{N}}) ( Π 0 N ) model T ( M ) = ⟨ X , { R a = m } Π 0 N , Val ⟩ \mathcal{T}(\mathcal{M}) = \langle X,\{R_{a=m}\}_{\Pi_0^{\mathbb{N}}},\operatorname{Val}\rangle T ( M ) = ⟨ X , { R a = m } Π 0 N , Val ⟩ by x R a = m y xR_{a=m}y x R a = m y if and only if R a ( x , y ) = m R_a(x,y) = m R a ( x , y ) = m .
The main result of this subsection shows that the translation τ \tau τ works as desired.
Theorem 5.4 (Translation Theorem). Let M \mathcal{M} M and T ( M ) \mathcal{T}(\mathcal{M}) T ( M ) be as in Definition 5.3. Then for every NPDL-formula φ \varphi φ and state x ∈ X x \in X x ∈ X it holds that
M , x ⊩ φ if and only if T ( M ) , x ⊩ τ ( φ ) . \mathcal{M},x \Vdash\varphi\quad\text{if and only if}\quad\mathcal{T}(\mathcal{M}),x \Vdash\tau(\varphi). M , x ⊩ φ if and only if T ( M ) , x ⊩ τ ( φ ) .
Proof. By simultaneous induction, for every formula φ \varphi φ we prove the above statement and for every program π \pi π we show the following (for all x , y ∈ X x,y \in X x , y ∈ X ):
R π ( x , y ) ≤ m if and only if x R τ ≤ m ( π ) y . R_\pi(x,y) \leq m \quad\text{if and only if}\quad xR_{\tau^{\leq m}(\pi)}y. R π ( x , y ) ≤ m if and only if x R τ ≤ m ( π ) y .
Formula induction. The base case p ∈ Φ 0 p \in\Phi_0 p ∈ Φ 0 is due to the fact that the same valuation Val \operatorname{Val} Val is used in M \mathcal{M} M and T ( M ) \mathcal{T}(\mathcal{M}) T ( M ) . The cases ¬ ψ \neg\psi ¬ ψ and ψ 1 ∧ ψ 2 \psi_1 \land\psi_2 ψ 1 ∧ ψ 2 are standard induction arguments.
Case ⟨ π ⟩ m φ \langle\pi\rangle^m\varphi ⟨ π ⟩ m φ : We have M , x ⊩ ⟨ π ⟩ m φ \mathcal{M},x \Vdash\langle\pi\rangle^m\varphi M , x ⊩ ⟨ π ⟩ m φ if and only if there is y ∈ X y \in X y ∈ X such that R π ( x , y ) ≤ m R_\pi(x,y) \leq m R π ( x , y ) ≤ m and M , y ⊩ φ \mathcal{M},y \Vdash\varphi M , y ⊩ φ . By the inductive hypothesis on π \pi π the former is equivalent to x R τ ≤ m ( π ) y xR_{\tau^{\leq m}(\pi)}y x R τ ≤ m ( π ) y and by the inductive hypothesis on φ \varphi φ the latter is equivalent to T ( M ) , y ⊩ τ ( φ ) \mathcal{T}(\mathcal{M}),y \Vdash\tau(\varphi) T ( M ) , y ⊩ τ ( φ ) . Thus M , x ⊩ φ \mathcal{M},x \Vdash\varphi M , x ⊩ φ if and only if T ( M ) , x ⊩ ⟨ τ ≤ m ( π ) ⟩ τ ( φ ) \mathcal{T}(\mathcal{M}),x \Vdash\langle\tau^{\leq m}(\pi)\rangle\tau(\varphi) T ( M ) , x ⊩ ⟨ τ ≤ m ( π )⟩ τ ( φ ) as desired (recall τ ( ⟨ π ⟩ m φ ) = ⟨ τ ≤ m ( π ) ⟩ τ ( φ ) \tau(\langle\pi\rangle^m\varphi) = \langle\tau^{\leq m}(\pi)\rangle\tau(\varphi) τ (⟨ π ⟩ m φ ) = ⟨ τ ≤ m ( π )⟩ τ ( φ ) ).
Program induction. The base case π = a ∈ Π 0 \pi= a \in\Pi_0 π = a ∈ Π 0 is immediate from the definitions.
x R τ ≤ m ( π 1 ∪ π 2 ) y ⟺ ( x , y ) ∈ R τ ≤ m ( π 1 ) ∪ R τ ≤ m ( π 2 ) (Def. τ ≤ m ( π 1 ∪ π 2 ) ) xR_{\tau^{\leq m}(\pi_1\cup\pi_2)}y \Longleftrightarrow(x,y) \in R_{\tau^{\leq m}(\pi_1)} \cup R_{\tau^{\leq m}(\pi_2)}
\qquad\text{(Def. }\tau^{\leq m}(\pi_1\cup\pi_2)\text{)} x R τ ≤ m ( π 1 ∪ π 2 ) y ⟺ ( x , y ) ∈ R τ ≤ m ( π 1 ) ∪ R τ ≤ m ( π 2 ) (Def. τ ≤ m ( π 1 ∪ π 2 ) )
⟺ R π 1 ( x , y ) ≤ m or R π 2 ( x , y ) ≤ m (IH on π 1 , π 2 ) \Longleftrightarrow R_{\pi_1}(x,y) \leq m\ \text{or}\ R_{\pi_2}(x,y) \leq m
\qquad\text{(IH on }\pi_1,\pi_2\text{)} ⟺ R π 1 ( x , y ) ≤ m or R π 2 ( x , y ) ≤ m (IH on π 1 , π 2 )
⟺ R π 1 ( x , y ) ∧ R π 2 ( x , y ) ≤ m ⟺ R π 1 ∪ π 2 ( x , y ) ≤ m . (Def. R π 1 ∪ π 2 ) \Longleftrightarrow R_{\pi_1}(x,y) \land R_{\pi_2}(x,y) \leq m
\Longleftrightarrow R_{\pi_1\cup\pi_2}(x,y) \leq m.
\qquad\text{(Def. }R_{\pi_1\cup\pi_2}\text{)} ⟺ R π 1 ( x , y ) ∧ R π 2 ( x , y ) ≤ m ⟺ R π 1 ∪ π 2 ( x , y ) ≤ m . (Def. R π 1 ∪ π 2 )
x R τ ≤ m ( π 1 ; π 2 ) y ⟺ ( x , y ) ∈ ⋃ i = 0 m R τ ≤ i ( π 1 ) ; R τ ≤ m − i ( π 2 ) xR_{\tau^{\leq m}(\pi_1;\pi_2)}y \Longleftrightarrow(x,y)\in\bigcup_{i=0}^{m}R_{\tau^{\leq i}(\pi_1)};R_{\tau^{\leq m-i}(\pi_2)} x R τ ≤ m ( π 1 ; π 2 ) y ⟺ ( x , y ) ∈ i = 0 ⋃ m R τ ≤ i ( π 1 ) ; R τ ≤ m − i ( π 2 )
(Def. τ ≤ m ( π 1 ; π 2 ) \tau^{\leq m}(\pi_1;\pi_2) τ ≤ m ( π 1 ; π 2 ) )
⟺ ⋁ i = 0 m ∃ v : ( x , v ) ∈ R τ ≤ i ( π 1 ) & ( v , y ) ∈ R τ ≤ m − i ( π 2 ) \Longleftrightarrow\bigvee_{i=0}^{m}\exists v:(x,v)\in R_{\tau^{\leq i}(\pi_1)}\mathbin{\&}(v,y)\in R_{\tau^{\leq m-i}(\pi_2)} ⟺ i = 0 ⋁ m ∃ v : ( x , v ) ∈ R τ ≤ i ( π 1 ) & ( v , y ) ∈ R τ ≤ m − i ( π 2 )
(Def. PDL-programs)
⟺ ⋁ i = 0 m ∃ z : R π 1 ( x , z ) ≤ i & R π 2 ( z , y ) ≤ m − i \Longleftrightarrow\bigvee_{i=0}^{m}\exists z:R_{\pi_1}(x,z)\leq i\mathbin{\&}R_{\pi_2}(z,y)\leq m-i ⟺ i = 0 ⋁ m ∃ z : R π 1 ( x , z ) ≤ i & R π 2 ( z , y ) ≤ m − i
(IH on π 1 , π 2 \pi_1,\pi_2 π 1 , π 2 )
⟺ ⋀ v ∈ X R π 1 ( x , v ) + R π 2 ( v , y ) ≤ m ⟺ R π 1 ; π 2 ( x , y ) ≤ m . \Longleftrightarrow\bigwedge_{v\in X}R_{\pi_1}(x,v)+R_{\pi_2}(v,y)\leq m\Longleftrightarrow R_{\pi_1;\pi_2}(x,y)\leq m. ⟺ v ∈ X ⋀ R π 1 ( x , v ) + R π 2 ( v , y ) ≤ m ⟺ R π 1 ; π 2 ( x , y ) ≤ m .
(Def. R π 1 ; π 2 R_{\pi_1;\pi_2} R π 1 ; π 2 )
x R τ ≤ 0 ( π ∗ ) y ⟺ x R τ ≤ 0 ( π ) ∗ y xR_{\tau^{\leq0}(\pi^*)}y\Longleftrightarrow xR^*_{\tau^{\leq0}(\pi)}y x R τ ≤ 0 ( π ∗ ) y ⟺ x R τ ≤ 0 ( π ) ∗ y
(Def. τ ≤ 0 ( π ∗ ) \tau^{\leq0}(\pi^*) τ ≤ 0 ( π ∗ ) )
⟺ x = y or ∃ v 1 , … , v k : x R τ ≤ 0 ( π ) v 1 … v k R τ ≤ 0 ( π ) y \Longleftrightarrow x=y\text{ or }\exists v_1,\ldots,v_k:xR_{\tau^{\leq0}(\pi)}v_1\ldots v_kR_{\tau^{\leq0}(\pi)}y ⟺ x = y or ∃ v 1 , … , v k : x R τ ≤ 0 ( π ) v 1 … v k R τ ≤ 0 ( π ) y
(Def. PDL-iteration)
⟺ x = y or ∃ v 1 , … , v k : R π ( x , v 1 ) ∧ ⋯ ∧ R π ( v k , y ) = 0 \Longleftrightarrow x=y\text{ or }\exists v_1,\ldots,v_k:R_\pi(x,v_1)\wedge\cdots\wedge R_\pi(v_k,y)=0 ⟺ x = y or ∃ v 1 , … , v k : R π ( x , v 1 ) ∧ ⋯ ∧ R π ( v k , y ) = 0
(IH on π \pi π )
⟺ R π ∗ ( x , y ) ≤ 0. \Longleftrightarrow R_{\pi^*}(x,y)\leq0. ⟺ R π ∗ ( x , y ) ≤ 0.
(Def. R π ∗ R_{\pi^*} R π ∗ )
For the inductive step, note that in the following we have i ≥ 1 i\geq1 i ≥ 1 , thus m − i < m m-i<m m − i < m .
x R τ ≤ 0 ( π ∗ ) y ⟺ ( x , y ) ∈ R τ ≤ 0 ( π ) ∗ ∪ ⋃ 1 ≤ i ≤ m R τ ≤ 0 ( π ∗ ) ; R τ ≤ i ( π ) ; R τ ≤ m − i ( π ∗ ) xR_{\tau^{\leq0}(\pi^*)}y\Longleftrightarrow(x,y)\in R^*_{\tau^{\leq0}(\pi)}\cup\bigcup_{1\leq i\leq m}R_{\tau^{\leq0}(\pi^*)};R_{\tau^{\leq i}(\pi)};R_{\tau^{\leq m-i}(\pi^*)} x R τ ≤ 0 ( π ∗ ) y ⟺ ( x , y ) ∈ R τ ≤ 0 ( π ) ∗ ∪ 1 ≤ i ≤ m ⋃ R τ ≤ 0 ( π ∗ ) ; R τ ≤ i ( π ) ; R τ ≤ m − i ( π ∗ )
⟺ R π ∗ ( x , y ) ≤ 0 or ⋁ 1 ≤ i ≤ m ∃ v 1 , v 2 : x R τ ≤ 0 ( π ∗ ) v 1 R τ ≤ i ( π ) v 2 R τ ≤ m − i ( π ∗ ) y \Longleftrightarrow R_{\pi^*}(x,y)\leq0\text{ or }\bigvee_{1\leq i\leq m}\exists v_1,v_2:xR_{\tau^{\leq0}(\pi^*)}v_1R_{\tau^{\leq i}(\pi)}v_2R_{\tau^{\leq m-i}(\pi^*)}y ⟺ R π ∗ ( x , y ) ≤ 0 or 1 ≤ i ≤ m ⋁ ∃ v 1 , v 2 : x R τ ≤ 0 ( π ∗ ) v 1 R τ ≤ i ( π ) v 2 R τ ≤ m − i ( π ∗ ) y
⟺ R π ∗ ( x , y ) ≤ 0 or ⋁ 1 ≤ i ≤ m ∃ v 1 , v 2 : R π ∗ ( x , v 1 ) ≤ 0 , R π ( v 1 , v 2 ) ≤ i , R π ∗ ( v 2 , y ) ≤ m − i \Longleftrightarrow R_{\pi^*}(x,y)\leq0\text{ or }\bigvee_{1\leq i\leq m}\exists v_1,v_2:R_{\pi^*}(x,v_1)\leq0,\ R_\pi(v_1,v_2)\leq i,\ R_{\pi^*}(v_2,y)\leq m-i ⟺ R π ∗ ( x , y ) ≤ 0 or 1 ≤ i ≤ m ⋁ ∃ v 1 , v 2 : R π ∗ ( x , v 1 ) ≤ 0 , R π ( v 1 , v 2 ) ≤ i , R π ∗ ( v 2 , y ) ≤ m − i
⟺ R π ∗ ( x , y ) ≤ m . \Longleftrightarrow R_{\pi^*}(x,y)\leq m. ⟺ R π ∗ ( x , y ) ≤ m .
The first ‘⟺ \Longleftrightarrow ⟺ ’ uses the definition of τ ≤ m ( π ∗ ) \tau^{\leq m}(\pi^*) τ ≤ m ( π ∗ ) , the second one uses the case m = 0 m=0 m = 0 and definition of PDL-programs, the third one uses the inductive hypothesis on π \pi π and m − i < m m-i<m m − i < m .
R φ ? ( x , y ) ≤ m ⟺ x = y and M , x ⊩ φ R_{\varphi?}(x,y)\leq m\Longleftrightarrow x=y\text{ and }\mathcal{M},x\Vdash\varphi R φ ? ( x , y ) ≤ m ⟺ x = y and M , x ⊩ φ
(Def. R φ ? R_{\varphi?} R φ ? )
⟺ x = y and T ( M ) , x ⊩ τ ( φ ) \Longleftrightarrow x=y\text{ and }T(\mathcal{M}),x\Vdash\tau(\varphi) ⟺ x = y and T ( M ) , x ⊩ τ ( φ )
(IH on φ \varphi φ )
⟺ x R τ ≤ m ( φ ? ) y . \Longleftrightarrow xR_{\tau^{\leq m}(\varphi?)}y. ⟺ x R τ ≤ m ( φ ?) y .
(Def. τ ≤ m ( φ ? ) \tau^{\leq m}(\varphi?) τ ≤ m ( φ ?) )
This finishes the proof. □ \square □
Recall that N ( φ ) N(\varphi) N ( φ ) is the largest index of modalities occurring in φ \varphi φ (Definition 3.9), furthermore we use ∣ φ ∣ |\varphi| ∣ φ ∣ to denote the length of φ \varphi φ (brackets and indices of modalities excluded). The following establishes the growth in size of a formula under the translation τ \tau τ in terms of these two parameters.
Lemma 5.5. For every formula φ \varphi φ , the length of τ ( φ ) \tau(\varphi) τ ( φ ) is O ( 2 2 ∣ φ ∣ N ( φ ) ∣ φ ∣ ) O(2^{2^{|\varphi|N(\varphi)}}|\varphi|) O ( 2 2 ∣ φ ∣ N ( φ ) ∣ φ ∣ ) . Similarly, for every program π \pi π , the length of τ ≤ m ( π ) \tau^{\leq m}(\pi) τ ≤ m ( π ) is O ( 2 ∣ π ∣ ( m + N ( π ) ) ∣ π ∣ ) O(2^{|\pi|(m+N(\pi))}|\pi|) O ( 2 ∣ π ∣ ( m + N ( π )) ∣ π ∣ ) .
Proof. Simultaneous induction on formula φ \varphi φ , program π \pi π and index m m m . The base cases of a ∈ Π 0 a\in\Pi_0 a ∈ Π 0 and p ∈ Φ 0 p\in\Phi_0 p ∈ Φ 0 are clear by definitions.
Formula Induction.
∣ τ ( ¬ φ ) ∣ = ∣ τ ( φ ) ∣ + 1 = O ( ( 2 2 ∣ φ ∣ N ( φ ) ∣ φ ∣ ) + 1 ) (Inductive Hypothesis) = O ( ( 2 2 ∣ φ ∣ N ( φ ) ) ( ∣ φ ∣ + 1 ) ) = O ( 2 2 ∣ ¬ φ ∣ N ( ¬ φ ) ∣ ¬ φ ∣ ) . \begin{aligned}
|\tau(\neg\varphi)|=|\tau(\varphi)|+1 \\
&=O((2^{2^{|\varphi|N(\varphi)}}|\varphi|)+1)
\qquad\text{(Inductive Hypothesis)} \\
&=O((2^{2^{|\varphi|N(\varphi)}})(|\varphi|+1)) \\
&=O(2^{2^{|\neg\varphi|N(\neg\varphi)}}|\neg\varphi|).
\end{aligned} ∣ τ ( ¬ φ ) ∣ = ∣ τ ( φ ) ∣ + 1 = O (( 2 2 ∣ φ ∣ N ( φ ) ∣ φ ∣ ) + 1 ) (Inductive Hypothesis) = O (( 2 2 ∣ φ ∣ N ( φ ) ) ( ∣ φ ∣ + 1 )) = O ( 2 2 ∣¬ φ ∣ N ( ¬ φ ) ∣¬ φ ∣ ) .
∣ τ ( φ 1 ∧ φ 2 ) ∣ = ∣ τ ( φ 1 ) ∣ + ∣ τ ( φ 2 ) ∣ + 1 = O ( 2 2 ∣ φ 1 ∣ N ( φ 1 ) ∣ φ 1 ∣ + 2 2 ∣ φ 2 ∣ N ( φ 2 ) ∣ φ 2 ∣ + 1 ) (Inductive Hypothesis) = O ( ( 2 2 ( ∣ φ 1 ∣ + ∣ φ 2 ∣ ) N ( φ 1 ∧ φ 2 ) ) ( ∣ φ 1 ∣ + ∣ φ 2 ∣ ) + 1 ) = O ( ( 2 2 ∣ φ 1 ∧ φ 2 ∣ N ( φ 1 ∧ φ 2 ) ) ∣ φ 1 ∧ φ 2 ∣ ) . \begin{aligned}
|\tau(\varphi_1 \land\varphi_2)| &= |\tau(\varphi_1)| + |\tau(\varphi_2)| + 1\\
&= O\left(2^{2|\varphi_1|N(\varphi_1)}|\varphi_1| + 2^{2|\varphi_2|N(\varphi_2)}|\varphi_2| + 1\right) \quad\text{(Inductive Hypothesis)}\\
&= O\left(\left(2^{2(|\varphi_1|+|\varphi_2|)N(\varphi_1\land\varphi_2)}\right)(|\varphi_1|+|\varphi_2|)+1\right)\\
&= O\left(\left(2^{2|\varphi_1\land\varphi_2|N(\varphi_1\land\varphi_2)}\right)|\varphi_1\land\varphi_2|\right).
\end{aligned} ∣ τ ( φ 1 ∧ φ 2 ) ∣ = ∣ τ ( φ 1 ) ∣ + ∣ τ ( φ 2 ) ∣ + 1 = O ( 2 2∣ φ 1 ∣ N ( φ 1 ) ∣ φ 1 ∣ + 2 2∣ φ 2 ∣ N ( φ 2 ) ∣ φ 2 ∣ + 1 ) (Inductive Hypothesis) = O ( ( 2 2 ( ∣ φ 1 ∣ + ∣ φ 2 ∣ ) N ( φ 1 ∧ φ 2 ) ) ( ∣ φ 1 ∣ + ∣ φ 2 ∣ ) + 1 ) = O ( ( 2 2∣ φ 1 ∧ φ 2 ∣ N ( φ 1 ∧ φ 2 ) ) ∣ φ 1 ∧ φ 2 ∣ ) .
∣ τ ( ⟨ π ⟩ m φ ) ∣ = ∣ τ ≤ m ( π ) ∣ + ∣ τ ( φ ) ∣ = O ( 2 2 ∣ φ ∣ N ( φ ) ∣ φ ∣ + 2 2 ∣ π ∣ ( m + N ( π ) ) ∣ π ∣ ) (Inductive Hypotheses) = O ( ( 2 2 ∣ φ ∣ N ( ⟨ π ⟩ m φ ) ∣ φ ∣ + 2 2 ∣ π ∣ N ( ⟨ π ⟩ m φ ) ) ∣ π ∣ ) ( m ≤ N ( ⟨ π ⟩ m φ ) ) = O ( 2 2 ∣ ⟨ π ⟩ m φ ∣ N ( ⟨ π ⟩ m φ ) ∣ ⟨ π ⟩ m φ ∣ ) . \begin{aligned}
|\tau(\langle\pi\rangle^m\varphi)| &= |\tau^{\leq m}(\pi)| + |\tau(\varphi)|\\
&= O\left(2^{2|\varphi|N(\varphi)}|\varphi| + 2^{2|\pi|(m+N(\pi))}|\pi|\right) \quad\text{(Inductive Hypotheses)}\\
&= O\left(\left(2^{2|\varphi|N(\langle\pi\rangle^m\varphi)}|\varphi| + 2^{2|\pi|N(\langle\pi\rangle^m\varphi)}\right)|\pi|\right) \quad(m \leq N(\langle\pi\rangle^m\varphi))\\
&= O\left(2^{2|\langle\pi\rangle^m\varphi|N(\langle\pi\rangle^m\varphi)}|\langle\pi\rangle^m\varphi|\right).
\end{aligned} ∣ τ (⟨ π ⟩ m φ ) ∣ = ∣ τ ≤ m ( π ) ∣ + ∣ τ ( φ ) ∣ = O ( 2 2∣ φ ∣ N ( φ ) ∣ φ ∣ + 2 2∣ π ∣ ( m + N ( π )) ∣ π ∣ ) (Inductive Hypotheses) = O ( ( 2 2∣ φ ∣ N (⟨ π ⟩ m φ ) ∣ φ ∣ + 2 2∣ π ∣ N (⟨ π ⟩ m φ ) ) ∣ π ∣ ) ( m ≤ N (⟨ π ⟩ m φ )) = O ( 2 2∣ ⟨ π ⟩ m φ ∣ N (⟨ π ⟩ m φ ) ∣ ⟨ π ⟩ m φ ∣ ) .
Program Induction.
∣ τ ≤ m ( π 1 ∪ π 2 ) ∣ = ∣ τ ≤ m ( π 1 ) ∣ + ∣ τ ≤ m ( π 2 ) ∣ + 1 = O ( ( 2 ∣ π 1 ∣ ( m + N ( π 1 ) ) ∣ π 1 ∣ + 2 ∣ π 2 ∣ ( m + N ( π 2 ) ) ∣ π 2 ∣ ) + 1 ) (Inductive Hypothesis) = O ( 2 ∣ π 1 ∪ π 2 ∣ ( m + N ( π 1 ∪ π 2 ) ) ( ∣ π 1 ∣ + ∣ π 2 ∣ + 1 ) ) = O ( 2 ∣ π 1 ∪ π 2 ∣ ( m + N ( π 1 ∪ π 2 ) ) ∣ π 1 ∪ π 2 ∣ ) . \begin{aligned}
|\tau^{\leq m}(\pi_1\cup\pi_2)| &= |\tau^{\leq m}(\pi_1)| + |\tau^{\leq m}(\pi_2)| + 1\\
&= O\left(\left(2^{|\pi_1|(m+N(\pi_1))}|\pi_1| + 2^{|\pi_2|(m+N(\pi_2))}|\pi_2|\right)+1\right) \quad\text{(Inductive Hypothesis)}\\
&= O\left(2^{|\pi_1\cup\pi_2|(m+N(\pi_1\cup\pi_2))}(|\pi_1|+|\pi_2|+1)\right)\\
&= O\left(2^{|\pi_1\cup\pi_2|(m+N(\pi_1\cup\pi_2))}|\pi_1\cup\pi_2|\right).
\end{aligned} ∣ τ ≤ m ( π 1 ∪ π 2 ) ∣ = ∣ τ ≤ m ( π 1 ) ∣ + ∣ τ ≤ m ( π 2 ) ∣ + 1 = O ( ( 2 ∣ π 1 ∣ ( m + N ( π 1 )) ∣ π 1 ∣ + 2 ∣ π 2 ∣ ( m + N ( π 2 )) ∣ π 2 ∣ ) + 1 ) (Inductive Hypothesis) = O ( 2 ∣ π 1 ∪ π 2 ∣ ( m + N ( π 1 ∪ π 2 )) ( ∣ π 1 ∣ + ∣ π 2 ∣ + 1 ) ) = O ( 2 ∣ π 1 ∪ π 2 ∣ ( m + N ( π 1 ∪ π 2 )) ∣ π 1 ∪ π 2 ∣ ) .
∣ τ ≤ m ( π 1 ; π 2 ) ∣ = ∣ ⋃ i = 0 m τ ≤ i ( π 1 ) ; τ ≤ m − i ( π 2 ) ∣ = ∑ i = 0 m ( ∣ τ ≤ i ( π 1 ) ∣ + ∣ τ ≤ m − i ( π 2 ) ∣ + 2 ) = O ( ∑ i = 0 m ( 2 ∣ π 1 ∣ ( i + N ( π 1 ) ) ∣ π 1 ∣ + 2 ∣ π 2 ∣ ( m − i + N ( π 2 ) ) ∣ π 2 ∣ + 2 ) ) (Inductive Hypothesis) = O ( 2 ∣ π 1 ∣ ( m + N ( π 1 ) ) + 1 ∣ π 1 ∣ + 2 ∣ π 2 ∣ ( m + N ( π 2 ) ) + 1 ∣ π 2 ∣ + 2 m ) ( ∑ i = 1 k 2 i ≤ 2 k + 1 ) = O ( 2 ( ∣ π 1 ∣ + ∣ π 2 ∣ + 1 ) ( m + N ( π 1 ; π 2 ) ) ( ∣ π 1 ∣ + ∣ π 2 ∣ + 1 ) ) = O ( 2 ∣ π 1 ; π 2 ∣ ( m + N ( π 1 ; π 2 ) ) ∣ π 1 ; π 2 ∣ ) . \begin{aligned}
|\tau^{\leq m}(\pi_1;\pi_2)| &= \left|\bigcup_{i=0}^{m}\tau^{\leq i}(\pi_1);\tau^{\leq m-i}(\pi_2)\right|\\
&= \sum_{i=0}^{m}\left(|\tau^{\leq i}(\pi_1)|+|\tau^{\leq m-i}(\pi_2)|+2\right)\\
&= O\left(\sum_{i=0}^{m}\left(2^{|\pi_1|(i+N(\pi_1))}|\pi_1|+2^{|\pi_2|(m-i+N(\pi_2))}|\pi_2|+2\right)\right) \quad\text{(Inductive Hypothesis)}\\
&= O\left(2^{|\pi_1|(m+N(\pi_1))+1}|\pi_1|+2^{|\pi_2|(m+N(\pi_2))+1}|\pi_2|+2m\right) \quad\left(\sum_{i=1}^{k}2^i\leq2^{k+1}\right)\\
&= O\left(2^{(|\pi_1|+|\pi_2|+1)(m+N(\pi_1;\pi_2))}(|\pi_1|+|\pi_2|+1)\right)\\
&= O\left(2^{|\pi_1;\pi_2|(m+N(\pi_1;\pi_2))}|\pi_1;\pi_2|\right).
\end{aligned} ∣ τ ≤ m ( π 1 ; π 2 ) ∣ = i = 0 ⋃ m τ ≤ i ( π 1 ) ; τ ≤ m − i ( π 2 ) = i = 0 ∑ m ( ∣ τ ≤ i ( π 1 ) ∣ + ∣ τ ≤ m − i ( π 2 ) ∣ + 2 ) = O ( i = 0 ∑ m ( 2 ∣ π 1 ∣ ( i + N ( π 1 )) ∣ π 1 ∣ + 2 ∣ π 2 ∣ ( m − i + N ( π 2 )) ∣ π 2 ∣ + 2 ) ) (Inductive Hypothesis) = O ( 2 ∣ π 1 ∣ ( m + N ( π 1 )) + 1 ∣ π 1 ∣ + 2 ∣ π 2 ∣ ( m + N ( π 2 )) + 1 ∣ π 2 ∣ + 2 m ) ( i = 1 ∑ k 2 i ≤ 2 k + 1 ) = O ( 2 ( ∣ π 1 ∣ + ∣ π 2 ∣ + 1 ) ( m + N ( π 1 ; π 2 )) ( ∣ π 1 ∣ + ∣ π 2 ∣ + 1 ) ) = O ( 2 ∣ π 1 ; π 2 ∣ ( m + N ( π 1 ; π 2 )) ∣ π 1 ; π 2 ∣ ) .
∣ τ ≤ 0 ( π ∗ ) ∣ = ∣ τ ≤ 0 ( π ) ∗ ∣ = O ( 2 ∣ π ∣ N ( π ) ∣ π ∣ + 1 ) (Inductive Hypothesis) = O ( 2 ∣ π ∣ N ( π ) ( ∣ π ∣ + 1 ) ) = O ( 2 ∣ π ∗ ∣ N ( π ∗ ) ∣ π ∗ ∣ ) . \begin{aligned}
|\tau^{\leq0}(\pi^*)| &= |\tau^{\leq0}(\pi)^*|\\
&= O\left(2^{|\pi|N(\pi)}|\pi|+1\right) \quad\text{(Inductive Hypothesis)}\\
&= O\left(2^{|\pi|N(\pi)}(|\pi|+1)\right)\\
&= O\left(2^{|\pi^*|N(\pi^*)}|\pi^*|\right).
\end{aligned} ∣ τ ≤ 0 ( π ∗ ) ∣ = ∣ τ ≤ 0 ( π ) ∗ ∣ = O ( 2 ∣ π ∣ N ( π ) ∣ π ∣ + 1 ) (Inductive Hypothesis) = O ( 2 ∣ π ∣ N ( π ) ( ∣ π ∣ + 1 ) ) = O ( 2 ∣ π ∗ ∣ N ( π ∗ ) ∣ π ∗ ∣ ) .
For m ≥ 1 m \ge1 m ≥ 1 , observe
∣ τ ≤ m ( π ∗ ) ∣ = ∣ τ ≤ 0 ( π ∗ ) ∪ ⋃ i = 1 m τ ≤ 0 ( π ∗ ) ; τ ≤ i ( π ) ; τ ≤ m − i ( π ∗ ) ∣ = ∣ τ ≤ 0 ( π ∗ ) ∣ + ∑ i = 1 m ( ∣ τ ≤ 0 ( π ∗ ) ∣ + ∣ τ ≤ i ( π ) ∣ + ∣ τ ≤ m − i ( π ∗ ) ∣ + 3 ) = O ( 2 ∣ π ∗ ∣ N ( π ∗ ) ∣ π ∗ ∣ + ∑ i = 1 m ( 2 ∣ π ∗ ∣ N ( π ∗ ) ∣ π ∗ ∣ + 2 ∣ π ∣ ( i + N ( π ) ) ∣ π ∣ + 2 ∣ π ∗ ∣ ( m − i + N ( π ∗ ) ) ∣ π ∗ ∣ + 3 ) ) = O ( 2 ∣ π ∗ ∣ M ( π ∗ ) ∣ π ∗ ∣ + m 2 ∣ π ∗ ∣ M ( π ∗ ) ∣ π ∗ ∣ + 2 ∣ π ∣ ( m + N ( π ) ) + 1 ∣ π ∣ + 2 ∣ π ∗ ∣ ( m + N ( π ∗ ) ) ∣ π ∗ ∣ + 3 m ) = O ( 2 ∣ π ∗ ∣ ( m + N ( π ∗ ) ) ∣ π ∗ ∣ ) . \begin{aligned}
|\tau^{\leq m}(\pi^*)| &= |\tau^{\leq0}(\pi^*) \cup\bigcup_{i=1}^{m}\tau^{\leq0}(\pi^*);\tau^{\leq i}(\pi);\tau^{\leq m-i}(\pi^*)| \\
&= |\tau^{\leq0}(\pi^*)|+\sum_{i=1}^{m}(|\tau^{\leq0}(\pi^*)|+|\tau^{\leq i}(\pi)|+|\tau^{\leq m-i}(\pi^*)|+3) \\
&= O(2^{|\pi^*|N(\pi^*)|\pi^*|}+\sum_{i=1}^{m}(2^{|\pi^*|N(\pi^*)}|\pi^*|+ \\
&\qquad2^{|\pi|(i+N(\pi))}|\pi|+2^{|\pi^*|(m-i+N(\pi^*))}|\pi^*|+3)) \\
&= O(2^{|\pi^*|M(\pi^*)}|\pi^*|+m2^{|\pi^*|M(\pi^*)}|\pi^*|+ \\
&\qquad2^{|\pi|(m+N(\pi))+1}|\pi|+2^{|\pi^*|(m+N(\pi^*))}|\pi^*|+3m) \\
&= O(2^{|\pi^*|(m+N(\pi^*))}|\pi^*|).
\end{aligned} ∣ τ ≤ m ( π ∗ ) ∣ = ∣ τ ≤ 0 ( π ∗ ) ∪ i = 1 ⋃ m τ ≤ 0 ( π ∗ ) ; τ ≤ i ( π ) ; τ ≤ m − i ( π ∗ ) ∣ = ∣ τ ≤ 0 ( π ∗ ) ∣ + i = 1 ∑ m ( ∣ τ ≤ 0 ( π ∗ ) ∣ + ∣ τ ≤ i ( π ) ∣ + ∣ τ ≤ m − i ( π ∗ ) ∣ + 3 ) = O ( 2 ∣ π ∗ ∣ N ( π ∗ ) ∣ π ∗ ∣ + i = 1 ∑ m ( 2 ∣ π ∗ ∣ N ( π ∗ ) ∣ π ∗ ∣ + 2 ∣ π ∣ ( i + N ( π )) ∣ π ∣ + 2 ∣ π ∗ ∣ ( m − i + N ( π ∗ )) ∣ π ∗ ∣ + 3 )) = O ( 2 ∣ π ∗ ∣ M ( π ∗ ) ∣ π ∗ ∣ + m 2 ∣ π ∗ ∣ M ( π ∗ ) ∣ π ∗ ∣ + 2 ∣ π ∣ ( m + N ( π )) + 1 ∣ π ∣ + 2 ∣ π ∗ ∣ ( m + N ( π ∗ )) ∣ π ∗ ∣ + 3 m ) = O ( 2 ∣ π ∗ ∣ ( m + N ( π ∗ )) ∣ π ∗ ∣ ) .
(Inductive Hypothesis)
∑ i = 1 k 2 i ≤ 2 k + 1 \sum_{i=1}^{k}2^i \leq2^{k+1} i = 1 ∑ k 2 i ≤ 2 k + 1
The last equality holds since m < 2 m m<2^m m < 2 m and ∣ π ∣ ( m + N ( π ) ) + 1 < ∣ π ∗ ∣ ( m + N ( π ∗ ) ) |\pi|(m+N(\pi))+1<|\pi^*|(m+N(\pi^*)) ∣ π ∣ ( m + N ( π )) + 1 < ∣ π ∗ ∣ ( m + N ( π ∗ )) , asymptotically the term 2 2 ∣ π ∣ ( m + M ( π ) ) + 1 ∣ π ∣ 2^{2|\pi|(m+M(\pi))+1}|\pi| 2 2∣ π ∣ ( m + M ( π )) + 1 ∣ π ∣ dominates all other terms in the preceding sum.
∣ τ ≤ m ( φ ? ) ∣ = ∣ τ ( φ ) ∣ + 1 = O ( 2 2 ∣ φ ∣ N ( φ ) ∣ φ ∣ + 1 ) \begin{aligned}
|\tau^{\leq m}(\varphi?)| &= |\tau(\varphi)|+1 \\
&= O(2^{2|\varphi|N(\varphi)}|\varphi|+1)
\end{aligned} ∣ τ ≤ m ( φ ?) ∣ = ∣ τ ( φ ) ∣ + 1 = O ( 2 2∣ φ ∣ N ( φ ) ∣ φ ∣ + 1 )
(Inductive Hypothesis)
= O ( ( 2 ∣ φ ∣ ( m + N ( φ ? ) ) ) ( ∣ φ ∣ + 1 ) ) = O ( 2 ∣ φ ? ∣ ( m + N ( φ ? ) ) ∣ φ ? ∣ ) \begin{aligned}
&= O((2^{|\varphi|(m+N(\varphi?))})(|\varphi|+1)) \\
&= O(2^{|\varphi?|(m+N(\varphi?))}|\varphi?|)
\end{aligned} = O (( 2 ∣ φ ∣ ( m + N ( φ ?)) ) ( ∣ φ ∣ + 1 )) = O ( 2 ∣ φ ? ∣ ( m + N ( φ ?)) ∣ φ ? ∣ )
(m = N ( φ ) m=N(\varphi) m = N ( φ ) by assumption)
This finishes the proof.
Note that this also indicates that NPDL is more succinct than PDL. Combining the above lemma this with the fact that PDL is EXPTIME-complete, we obtain our upper complexity bound.
Corollary 5.6 (Upper Bound). The satisfiability problem of NPDL is in 2 2 2 EXPTIME.
Remark 5.7 (Adding converse and intersection). The translation τ \tau τ can be extended to converse programs π ⌣ \pi^\smile π ⌣ interpreted as R π ⌣ ( x , y ) = R π ( y , x ) R_{\pi^\smile}(x,y)=R_\pi(y,x) R π ⌣ ( x , y ) = R π ( y , x ) via τ ≤ m ( π ⌣ ) = τ ≤ m ( π ) ⌣ \tau^{\leq m}(\pi^\smile)=\tau^{\leq m}(\pi)^\smile τ ≤ m ( π ⌣ ) = τ ≤ m ( π ) ⌣ , hence we obtain the same complexity bounds for this extension. Similarly, τ \tau τ can be extended to concurrent NPDL [4 ] with intersection generalized by R π 1 ∩ π 2 ( x , y ) = R π 1 ( x , y ) ∨ R π 2 ( x , y ) R_{\pi_1\cap\pi_2}(x,y)=R_{\pi_1}(x,y)\lor R_{\pi_2}(x,y) R π 1 ∩ π 2 ( x , y ) = R π 1 ( x , y ) ∨ R π 2 ( x , y ) via τ ≤ m ( π 1 ∩ π 2 ) = τ ≤ m ( π 1 ) ∩ τ ≤ m ( π 2 ) \tau^{\leq m}(\pi_1\cap\pi_2)=\tau^{\leq m}(\pi_1)\cap\tau^{\leq m}(\pi_2) τ ≤ m ( π 1 ∩ π 2 ) = τ ≤ m ( π 1 ) ∩ τ ≤ m ( π 2 ) . Hence we obtain decidability of concurrent NPDL and from 2 2 2 EXPTIME-completeness of concurrent PDL [16 ] we obtain a 3 3 3 EXPTIME-upper bound.
The Model Checking Problem
In this subsection, we show that given a NPDL model M = ( X , R a , Val ) \mathcal{M}=(X,R_a,\operatorname{Val}) M = ( X , R a , Val ) , a state x ∈ X x\in X x ∈ X , and a formula φ \varphi φ , we can check whether M , x ⊨ φ \mathcal{M},x\models\varphi M , x ⊨ φ in time O ( ∣ M ∣ 3 ∣ φ ∣ ) O(|\mathcal{M}|^3|\varphi|) O ( ∣ M ∣ 3 ∣ φ ∣ ) . The model checking is performed by computing the set of worlds in M \mathcal{M} M which satisfy φ \varphi φ (denoted by [ [ φ ] ] [\![\varphi]\!] [ [ φ ] ] ) through the following recursive steps on the complexity of φ \varphi φ .
[ [ p ] ] : = Val ( p ) [\![p]\!]:=\operatorname{Val}(p) [ [ p ] ] := Val ( p ) .
[ [ φ 1 ∧ φ 2 ] ] : = [ [ φ 1 ] ] ∩ [ [ φ 2 ] ] [\![\varphi_1\land\varphi_2]\!]:=[\![\varphi_1]\!]\cap[\![\varphi_2]\!] [ [ φ 1 ∧ φ 2 ] ] := [ [ φ 1 ] ] ∩ [ [ φ 2 ] ] .
[ [ ¬ φ ] ] : = X \ [ [ φ ] ] [\![\neg\varphi]\!]:=X\backslash[\![\varphi]\!] [ [ ¬ φ ] ] := X \ [ [ φ ] ] .
[ [ ⟨ π ⟩ m φ ] ] : = π ≤ m − 1 ( [ [ φ ] ] ) = { x ∣ ∃ y ∈ [ [ φ ] ] : ( R π ( x , y ) ≤ m ) } [\![\langle\pi\rangle^m\varphi]\!]:=\pi^{\leq m-1}([\![\varphi]\!])=\{x\mid\exists y\in[\![\varphi]\!]: (R_\pi(x,y)\leq m)\} [ [⟨ π ⟩ m φ ] ] := π ≤ m − 1 ([ [ φ ] ]) = { x ∣ ∃ y ∈ [ [ φ ] ] : ( R π ( x , y ) ≤ m )} .
For any x , y ∈ X x,y\in X x , y ∈ X , and any program π \pi π , given R a ( x , y ) R_a(x,y) R a ( x , y ) for any atomic program a a a occurring in π \pi π , we compute R π ( x , y ) R_\pi(x,y) R π ( x , y ) by the following recursion.
R π 1 ∪ π 2 ( x , y ) = min ( R π 1 ( x , y ) , R π 2 ( x , y ) ) . (1) R_{\pi_1\cup\pi_2}(x,y)=\min(R_{\pi_1}(x,y),R_{\pi_2}(x,y)). \tag*{(1)} R π 1 ∪ π 2 ( x , y ) = min ( R π 1 ( x , y ) , R π 2 ( x , y )) . (1)
R π 1 ∘ π 2 ( x , y ) = min v ∈ X R π 1 ( x , v ) + R π 2 ( v , y ) . (2) R_{\pi_1\circ\pi_2}(x,y)=\min_{v\in X}R_{\pi_1}(x,v)+R_{\pi_2}(v,y). \tag*{(2)} R π 1 ∘ π 2 ( x , y ) = v ∈ X min R π 1 ( x , v ) + R π 2 ( v , y ) . (2)
For any π \pi π , given R π R_\pi R π , we can compute R π ∗ R_{\pi^*} R π ∗ in time O ( ∣ M ∣ 3 ) O(|\mathcal{M}|^3) O ( ∣ M ∣ 3 ) using the Floyd–Warshall algorithm [7 , 25 ] .
Proposition 5.8. Let π \pi π be a program and φ \varphi φ be a formula.
The relation R π R_\pi R π can be computed in time O ( ∣ M ∣ 3 ∣ π ∣ ) O(|\mathcal{M}|^3|\pi|) O ( ∣ M ∣ 3 ∣ π ∣ ) .
The set [ [ φ ] ] [\![\varphi]\!] [ [ φ ] ] can be computed in time O ( ∣ M ∣ 3 ∣ φ ∣ ) O(|\mathcal{M}|^3|\varphi|) O ( ∣ M ∣ 3 ∣ φ ∣ ) .
Proof. By simultaneous induction we show (1) for every program π \pi π and (2) for every formula φ \varphi φ .
Program Induction. The base case is trivially true.
Case π 1 ∪ π 2 \pi_1\cup\pi_2 π 1 ∪ π 2 : If R π 1 R_{\pi_1} R π 1 and R π 2 R_{\pi_2} R π 2 are already computed, we need to perform one new operation (taking minimum) for any pair of points x , y ∈ X x,y\in X x , y ∈ X . Therefore (using the inductive hypothesis), the total number of steps in this computation is bounded by O ( ∣ M ∣ 3 ∣ π 1 ∣ ) + O ( ∣ M ∣ 3 ∣ π 2 ∣ ) + O ( ∣ M ∣ 2 ) = O ( ∣ M ∣ 3 ∣ π 1 ∪ π 2 ∣ ) O(|\mathcal{M}|^3|\pi_1|)+O(|\mathcal{M}|^3|\pi_2|)+O(|\mathcal{M}|^2)=O(|\mathcal{M}|^3|\pi_1\cup\pi_2|) O ( ∣ M ∣ 3 ∣ π 1 ∣ ) + O ( ∣ M ∣ 3 ∣ π 2 ∣ ) + O ( ∣ M ∣ 2 ) = O ( ∣ M ∣ 3 ∣ π 1 ∪ π 2 ∣ ) .
Case π 1 ; π 2 \pi_1;\pi_2 π 1 ; π 2 : If R π 1 R_{\pi_1} R π 1 and R π 2 R_{\pi_2} R π 2 are already computed, we need to perform two new operations (taking sum and minimum) for any triplet of points x , v , y ∈ W x,v,y\in W x , v , y ∈ W . Therefore (by the inductive hypothesis), the total number of steps in the computation is bounded by O ( ∣ M ∣ 3 ∣ π 1 ∣ ) + O ( ∣ M ∣ 3 ∣ π 2 ∣ ) + O ( ∣ M ∣ 3 ) = O ( ∣ M ∣ 3 ∣ π 1 ∘ π 2 ∣ ) O(|\mathcal{M}|^3|\pi_1|)+O(|\mathcal{M}|^3|\pi_2|)+O(|\mathcal{M}|^3)=O(|\mathcal{M}|^3|\pi_1\circ\pi_2|) O ( ∣ M ∣ 3 ∣ π 1 ∣ ) + O ( ∣ M ∣ 3 ∣ π 2 ∣ ) + O ( ∣ M ∣ 3 ) = O ( ∣ M ∣ 3 ∣ π 1 ∘ π 2 ∣ ) .
Case π ∗ \pi^* π ∗ : We need to do O ( ∣ M ∣ 3 ) O(|\mathcal{M}|^3) O ( ∣ M ∣ 3 ) new operations using the Floyd–Warshall algorithm. Therefore, by induction, the total number of operations is bounded by O ( ∣ M ∣ 3 ∣ π ∣ ) + O ( ∣ M ∣ 3 ) = O ( ∣ M ∣ 3 ∣ π ∗ ∣ ) O(|\mathcal{M}|^3|\pi|)+O(|\mathcal{M}|^3)=O(|\mathcal{M}|^3|\pi^*|) O ( ∣ M ∣ 3 ∣ π ∣ ) + O ( ∣ M ∣ 3 ) = O ( ∣ M ∣ 3 ∣ π ∗ ∣ ) .
Case π = φ ? \pi=\varphi? π = φ ? : By definition, R φ ? = [ [ φ ] ] × [ [ φ ] ] R_{\varphi?}=[\![\varphi]\!]\times[\![\varphi]\!] R φ ? = [ [ φ ] ] × [ [ φ ] ] . Therefore by induction, the total number of operations is bounded by O ( ∣ M ∣ 3 ∣ φ ∣ ) + O ( ∣ M ∣ 2 ) = O ( ∣ M ∣ 3 ∣ φ ? ∣ ) O(|\mathcal{M}|^3|\varphi|)+O(|\mathcal{M}|^2)=O(|\mathcal{M}|^3|\varphi?|) O ( ∣ M ∣ 3 ∣ φ ∣ ) + O ( ∣ M ∣ 2 ) = O ( ∣ M ∣ 3 ∣ φ ? ∣ ) .
Formula Induction. The base case is trivially true.
Case φ = φ 1 ∧ φ 2 \varphi=\varphi_1\land\varphi_2 φ = φ 1 ∧ φ 2 : Since [ [ φ ] ] = [ [ φ 1 ] ] ∩ [ [ φ 2 ] ] [\![\varphi]\!]=[\![\varphi_1]\!]\cap[\![\varphi_2]\!] [ [ φ ] ] = [ [ φ 1 ] ] ∩ [ [ φ 2 ] ] , we need to do O ( ∣ M ∣ ) O(|\mathcal{M}|) O ( ∣ M ∣ ) new operations. Therefore, the total number of operations is bounded by O ( ∣ M ∣ 3 ∣ φ 1 ∣ ) + O ( ∣ M ∣ 3 ∣ φ 2 ∣ ) + O ( ∣ M ∣ ) = O ( ∣ M ∣ 3 ∣ φ 1 ∧ φ 2 ∣ ) O(|\mathcal{M}|^3|\varphi_1|)+O(|\mathcal{M}|^3|\varphi_2|)+O(|\mathcal{M}|)=O(|\mathcal{M}|^3|\varphi_1\land\varphi_2|) O ( ∣ M ∣ 3 ∣ φ 1 ∣ ) + O ( ∣ M ∣ 3 ∣ φ 2 ∣ ) + O ( ∣ M ∣ ) = O ( ∣ M ∣ 3 ∣ φ 1 ∧ φ 2 ∣ ) .
Case φ = ¬ φ 1 \varphi=\neg\varphi_1 φ = ¬ φ 1 : Since [ [ φ ] ] = X \ [ [ φ 1 ] ] [\![\varphi]\!]=X\backslash[\![\varphi_1]\!] [ [ φ ] ] = X \ [ [ φ 1 ] ] , we need to do O ( ∣ M ∣ ) O(|\mathcal{M}|) O ( ∣ M ∣ ) new operations. Therefore, the total number of operations is bounded by O ( ∣ M ∣ 3 ∣ φ 1 ∣ ) + O ( ∣ M ∣ ) = O ( ∣ M ∣ 3 ∣ ¬ φ 1 ∣ ) O(|\mathcal{M}|^3|\varphi_1|)+O(|\mathcal{M}|)=O(|\mathcal{M}|^3|\neg\varphi_1|) O ( ∣ M ∣ 3 ∣ φ 1 ∣ ) + O ( ∣ M ∣ ) = O ( ∣ M ∣ 3 ∣¬ φ 1 ∣ ) .
Case φ = ⟨ π ⟩ m φ 1 \varphi=\langle\pi\rangle^m\varphi_1 φ = ⟨ π ⟩ m φ 1 : since [ [ φ ] ] = { x ∣ ∃ y ∈ [ [ φ 1 ] ] ( R π ( x , y ) ≤ m ) } [\![\varphi]\!]=\{x\mid\exists y\in[\![\varphi_1]\!](R_\pi(x,y)\le m)\} [ [ φ ] ] = { x ∣ ∃ y ∈ [ [ φ 1 ] ] ( R π ( x , y ) ≤ m )} , we need to do O ( ∣ M ∣ 2 ) O(|\mathcal{M}|^2) O ( ∣ M ∣ 2 ) new operations. Therefore, the total number of operations is bounded by O ( ∣ M ∣ 3 ∣ φ 1 ∣ ) + O ( ∣ M ∣ 3 ∣ π ∣ ) + O ( ∣ M ∣ 2 ) = O ( ∣ M ∣ 3 ∣ ⟨ π ⟩ m φ 1 ∣ ) O(|\mathcal{M}|^3|\varphi_1|)+O(|\mathcal{M}|^3|\pi|)+O(|\mathcal{M}|^2)=O(|\mathcal{M}|^3|\langle\pi\rangle^m\varphi_1|) O ( ∣ M ∣ 3 ∣ φ 1 ∣ ) + O ( ∣ M ∣ 3 ∣ π ∣ ) + O ( ∣ M ∣ 2 ) = O ( ∣ M ∣ 3 ∣ ⟨ π ⟩ m φ 1 ∣ ) .
In conclusion, we obtain the following complexity bound on the model checking problem. Note that this bound is a significant improvement over the naive bound obtained by the translation of NPDL into PDL of the previous subsection.
Corollary 5.9. The model checking problem of NPDL is in O ( ∣ M ∣ 3 ∣ φ ∣ ) O(|\mathcal{M}|^3|\varphi|) O ( ∣ M ∣ 3 ∣ φ ∣ ) .
Conclusion and Future Research
We introduced NPDL, a variant of propositional dynamic logic interpreted on N ∞ \mathbb{N}^{\infty} N ∞ -weighted frames with modalities ⟨ π ⟩ m \langle\pi\rangle^m ⟨ π ⟩ m describing accessibility with resource-consumption at most m ∈ N m\in\mathbb{N} m ∈ N . Showing that satisfiability can be checked on finite models of bounded size and with bounded weights, we proved that NPDL is decidable. Combining filtration techniques with the canonical model construction, we showed completeness. Lastly, using translations into standard PDL we obtained complexity bounds for NPDL.
In this work, we have provided a 2EXPTIME-upper bound on the complexity of NPDL. The main open question at this point is whether that bound is strict, or whether NPDL remains EXPTIME-complete (e.g. for the case of PDL, see Pratt’s algorithm [19 ] ). This problem also remains open for extensions of NPDL with additional program constructs such as converse and intersection (recall Remark 5.7).
Another question is whether NPDL has Craig Interpolation , a property which has only recently been shown for standard PDL [2 ] and converse PDL [11 ] . Related to this, in future work we aim to develop the proof theory of NPDL, for instance via cyclic tableaux systems where linear inequalities of weights are explicitly included in the syntax.
For further future research directions we propose to consider cost-sensitive variants of extensions and generalizations of PDL, for instance of Game Logic [17 , 18 ] or (first-order) Dynamic Logic [10 Chapter 11] . One may also consider other quantales than N ∞ N^{\infty} N ∞ to represent resources, making it more challenging to come up with a finitary axiomatization (note that our reduction axioms depend on the fact that there are only finitely many ways to write n n n as a binary sum). In addition, it would be interesting to investigate the relation of NPDL to many-valued versions of PDL previously proposed for modeling program costs [3 , 20 , 21 ] or to graded-belief based programs [13 , 14 ] . Lastly, let us mention that for such an analysis the coalgebraic perspective [8 , 9 ] (also see Remark 2.5) is promising.
Acknowledgments
Funded by the European Union under the Operational Programme Jan Amos Komenský project no. CZ.02.01.01/00/23_025/0008724. The second author was furthermore supported by the European Research Executive Agency ERA Fellowship project no. 101334342. Institute of Computer Science of the Czech Academy of Sciences, Prague
Email address: manoorkar@cs.cas.cz, poiger@cs.cas.cz