On Graded Concurrent PDL
CHUN-YU LIN · 2025
Read On Graded Concurrent PDL by CHUN-YU LIN (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-09285.txt.
Introduction
Chun-Yu Lin grades a logic for programs that run side by side in a 2025 paper. The base logic reasons about steps a program can take. A later form added programs that run at the same time.
Lin lets truth and reach take grades on a short finite scale, not just yes or no. That graded form suits reasoning when facts are unsure. He proves the rule set is complete for all finite valued forms of the logic. In plain terms, each true claim in the graded system can be reached by the rules, and no false one can.
Catalog record
| CREATOR | CHUN-YU LIN |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-09285
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Graded Concurrent PDL CHUN-YU LIN Abstract Propositional Dynamic Logic, 𝖯𝖣𝖫 \mathsf{PDL} , is a modal logic designed to formalize the reasoning about programs. By extending accessibility between states to states and state sets, concurrent propositional dynamic logic 𝖢𝖯𝖣𝖫 \mathsf{CPDL} , is introduced to include concurrent programs due to Peleg and Goldblatt. We study a many-valued generalization of 𝖢𝖯𝖣𝖫 \mathsf{CPDL} where the satisfiability and the reachability relation between states and state sets are graded over a finite Łukasiewicz chain. Finitely-valued dynamic logic has been shown to be useful in formalizing reasoning about program behaviors under uncertainty. We obtain completeness results for all finitely valued 𝖯𝖣𝖫 \mathsf{PDL} . 1 Introduction Propositional dynamic logic, \mathsf{PDL} , has been introduced as a logic of imperative computer programs [ 5 ] , but it has found many applications in formalizing reasoning about actions in general. Many-valued versions of \mathsf{PDL} aim at formalizing reasoning about action in contexts where imprecise concepts are involved (e.g., [ 12 ] ). For example, goals may be specified using vague notions, or weights may be attached to actions depending on the amount of resources their execution consumes. The concurrent propositional dynamic logic \mathsf{CPDL} [ 6 , 10 ] extends \mathsf{PDL} with an operator representing the parallel execution of two actions: \scalebox{0.9}{{[}}\alpha\cap\beta\scalebox{0.9}{{]}}\varphi means that a successful parallel execution of action \alpha and \beta is guaranteed to make \varphi true. In this paper, we outline a version with many values of \mathsf{CPDL} . Our logic is based on propositional dynamic models in which formulas and accessibility relations are evaluated in finite Łukasiewicz chains; therefore, we extend the framework of [ 12 ] with the parallel execution operator. Our main technical result is a soundness and completeness theorem for logic. 2 Concurrent PDL over Ł n Let \Pi be a countable set of program variables \pi_{0},\pi_{1}.\ldots which are used to denote the atomic programs. The intrinsic meaning of atomic programs is not examined further. Instead, we concentrate on the complex programs generated by operations on the given ones. Let P be a countable set of propositional variables. Let Ł n be a finite Łukasiewicz chain. The language \mathcal{L}_{n} for concurrent propositional dynamic logic can be separated into two categories-the set of programs \Pi_{n} and formulas \Phi_{n} defined mutually recursively in Barckus-Naur form as follows: • \Pi_{n} \pi\coloneqq\bar{\pi}\;|\;\pi_{0}\cup\pi_{1}\;|\;\pi_{0}\cap\pi_{1}\;|\;\pi_{0};\pi_{1}\;|\;\pi^{*}\;|\;\varphi? • \Phi_{n} \varphi\coloneqq p\;|\;\bar{c}\;|\;\varphi_{0}\vee\varphi_{1}\;|\;\varphi_{0}\wedge\varphi_{1}\;|\;\varphi_{0}\to\varphi_{1}\;|\;[\pi]\varphi\;|\;\langle\pi\rangle\varphi where \bar{\pi}\in\Pi , p\in\textbf{P} and c\in Ł n . From [ 7 ] , we know that two modal operators [\pi] and \langle\pi\rangle are not interdefinable via \neg in concurrent PDL. The intended meanings for the operations on the programs are as follows. • \pi_{0};\pi_{1} execute \pi_{0} then \pi_{1} , • \pi_{0}\cup\pi_{1} execute \pi_{0} or \pi_{1} non-deterministically, • \pi_{0}\cap\pi_{1} execute \pi_{0} and \pi_{1} concurrently, • \pi^{*} execute \pi for some finite number of times, • \varphi? test \varphi : if \varphi is true, then continue; otherwise fail. In the context of concurrency, the results of execution of an initial state s will be a set of states T rather than a single state. Therefore, the accessibility relation on a set S in Kripke semantics of propositional dynamic logic should be generalized to a set of pair \langle s,T\rangle , with s\in S and T\subseteq S . We then call the graded accessibility relation as a reachable \textbf{\L}_{n} -relation. Definition 1 A reachable \textbf{\L}_{n} -relation on a set S is a function from S\times\mathcal{P}(S) to \textbf{\L}_{n} . The operations on reachable \textbf{\L}_{n} -relation are defined as another reachable \textbf{\L}_{n} -relations in the following paragraph. Definition 2 Let R,Q be two reachable \textbf{\L}_{n} -relations on a set S , s\in S and T,W\subseteq S . • \iota(s,T)=\begin{cases}1&\text{if }T=\{s\}\\ 0&\text{otherwise}\\ \end{cases} , • (R\cup Q)(s,T)=\bigvee_{t\in T}(R(s,T)\vee Q(s,T)) , • (R\circ Q)(s,T)=\bigvee_{U\subseteq S}\bigvee\{R(s,U)\odot\bigodot_{u\in U}Q(u,T_{u})|T=\bigcup_{u\in U}T_{u}\} , • R^{(0)}=\iota , R^{(n+1)}=\iota\cup(R\circ R^{(n)}) , and R^{*}=\bigvee\{R^{(n)}|n\geq 0\} , • (R\otimes Q)(s,T\cup W)=R(s,T)\odot Q(s,W) . Lemma 1 For any reachable \textbf{\L}_{n} -relations Q,Q^{\prime},R,R^{\prime} on a set S , we have the following properties. 1. Q\leq Q^{\prime} implies R\circ Q\leq R\circ Q^{\prime} 2. (R\cup R^{\prime})\circ Q=R\circ Q\cup R^{\prime}\circ Q 3. R^{(n)}\leq R^{(n+1)} A \textbf{\L}_{n} -valuation \nu is any non-modal homomorphism from \mathcal{L}_{n} to \textbf{\L}_{n} , i.e. \nu:\mathcal{L}_{n}\to\textbf{\L}_{n} such that \nu(\bar{c})=c, and \nu(\varphi\star\psi)=\nu(\varphi)\ast\nu(\psi) where \star,\ast\in\{\wedge,\vee,\to\} denote the Boolean operations and \textbf{L}_{n} -operations respectively. Definition 3 Let \Theta be a set of formulas and \varphi be a formula in \mathcal{L}_{n} . We say that \varphi is a \textbf{\L}_{n} -semantics consequence of \Theta if \nu[\Theta]=\{1\}\text{ implies }\nu(\varphi)=1 for any \textbf{\L}_{n} -valuation \nu . In this case, we write \Theta\Vdash_{\textbf{\L}_{n}}\varphi . We then introduce the world semantics for concurrent PDL. Definition 4 A \textbf{\L}_{n} -frame is a pair \mathcal{F}=\langle S,R\rangle , where S is a nonempty set and R:\Pi\to\textbf{\L}_{n}^{S\times\mathcal{P}(S)} . A \textbf{\L}_{n} -model is M=\langle S,R,V\rangle where \langle S,R\rangle is a \textbf{\L}_{n} -frame and V:\textbf{P}\to{\textbf{\L}_{n}}^{S} . Given a \textbf{\L}_{n} -model M , the M -interpretation is a function \mathcal{I}_{M}:((\Pi_{n}\times S\times\mathcal{P}(S))\cup(\Phi_{n}\times S))\to\textbf{\L}_{n} such that for any \bar{\pi}\in\Pi,\pi_{0},\pi_{1}\in\Pi_{n},s\in S,T\in\mathcal{P}(S),p\in\textbf{P},c\in\textbf{\L}_{n} , and \varphi,\psi\in\mathcal{L}_{n} : • \mathcal{I}_{M}(\bar{\pi},s,T)=R(\bar{\pi})(s,T) , • \mathcal{I}_{M}(p,s)=V(p)(s) , • \mathcal{I}_{M}(\bar{c},s)=c , • \mathcal{I}_{M}(\varphi\star\phi,s)=\mathcal{I}_{M}(s)\ast\mathcal{I}_{M}(s) where \star,\ast\in\{\wedge,\vee,\to\} denote the boolean operations and \textbf{L}_{n} -operations respectively, • \mathcal{I}_{M}([\pi]\varphi,s)=\bigwedge_{T\subseteq S}(\mathcal{I}_{M}(\pi,s,T)\to\bigwedge_{t\in T}\mathcal{I}_{M}(\varphi,t)) , • \mathcal{I}_{M}(\langle\pi\rangle\varphi,s)=\bigvee_{T\subseteq S}(\mathcal{I}_{M}(\pi,s,T)\odot\bigwedge_{t\in T}\mathcal{I}_{M}(\varphi,t)) Denote \mathcal{I}_{M}(\pi,s,T) as a \textbf{L}_{n} -reachable relation R_{\pi}(s,T) • \mathcal{I}_{M}(\pi_{0}\cup\pi_{1},s,T)=(R_{\pi_{0}}\cup R_{\pi_{1}})(s,T) , • \mathcal{I}_{M}(\pi_{0};\pi_{1},s,T)=(R_{\pi_{0}}\circ R_{\pi_{1}})(s,T) , • \mathcal{I}_{M}(\pi_{0}\cap\pi_{1},s,T)=(R_{\pi_{0}}\otimes R_{\pi_{1}})(s,T) , • \mathcal{I}_{M}(\pi^{*},s,T)=(R_{\pi})^{*}(s,T) , • \mathcal{I}_{M}(\varphi?,s,T)=\begin{cases}\mathcal{I}_{M}(\varphi,s)&\text{if }T=\{s\}\\ 0&\text{otherwise.}\\ \end{cases} Clearly, fixed an s\in S , a M -interpretation is a \textbf{\L}_{n} -valuation. A formula \varphi is called valid in a \textbf{\L}_{n} -model M if \mathcal{I}_{M}(\varphi,s)=1 for all s\in S . 3 Finite MV-chains We briefly introduce the definitions and basic properties of finite MV-chains in this section. From more detailed introduction, we refer to the handbooks [ 4 ] . Definition 5 A finite MV-chain is an algebraic structure \text{\L}_{n}=\langle A,\lor,\land,\to,\odot,\bar{0},\bar{1}\rangle with |A|=n such that : • \langle A,\lor,\land,\bar{0},\bar{1}\rangle is a finite bounded lattice, • \langle A,\odot,\bar{1}\rangle is a finite commutative monoid, • Define the total ordering \leq as a\leq b iff a\land b=b iff a\lor b=a , • \odot is residuated with \to , i.e. for all a,b,c\in A , a\odot b\leq c iff b\leq a\to c , • (a\to b)\vee(b\to a)=\bar{1} for all a,b\in A . • a\wedge b=a\odot(a\to b) for all a,b\in A . • Define \neg a\coloneqq a\to\bar{0} satisfying \neg\neg a=a for all a\in A . The above definition is an abstract formulation. According to Corollary 3.5.4 in [ 3 ] , any finite MV-chain \text{\L}_{n} is isomorphic to the following more concrete finite MV-chains \textbf{\L}_{n} for any n\geq 2 . \textbf{\L}_{n}=\langle\{\frac{0}{n-1},\frac{1}{n-1},\ldots,\frac{n-1}{n-1}\},\to,\odot,\sim,\bar{0},\bar{1}\rangle where a\odot b\coloneqq max\{0,a+b-1\} , a\to b\coloneqq min\{1,1-a+b\} , and \sim a\coloneqq 1-a for any a,b\in\{\frac{0}{n-1},\frac{1}{n-1},\ldots,\frac{n-1}{n-1}\} . Note that a\vee b\coloneqq(a\to b)\to b(=max\{a,b\}) and a\wedge b\coloneqq a\odot(a\to b)(=min\{a,b\}) . The truncated addition \odot is the Łukasiewicz t-norm. In this article, we will use \textbf{\L}_{n} as our definition of finite MV-chain. 4 Proof System For each n\geq 2 , the axiomatic system \textbf{P\L}_{n} is a Hilbert-style proof system consists the following axiom schemata and rule : • \varphi\to(\psi\to\varphi) , • (\varphi\to\psi)\to((\psi\to\chi)\to(\varphi\to\chi)) , • ((\varphi\to\psi)\to\psi)\to((\psi\to\varphi)\to\varphi) , • (\neg\psi\to\neg\varphi)\to(\varphi\to\psi) , • \overline{c\ast d}\leftrightarrow\bar{c}\star\bar{d} where \star,\ast\in\{\wedge,\vee,\to\} denote the boolean operations and \textbf{L}_{n} -operations respectively, • (MP): from \varphi and \varphi\to\psi infer \psi . We give the definition of a formula \varphi being derivable in \textbf{P\L}_{n} from a set of formulas \Theta