Formula Synthesis in Propositional Dynamic Logic with Shuffle

Sophie Pinchinat, Sasha Rubin, François SchwarzentruberAAAI 2022 · DOI

Abstract

This paper explores the formula-synthesis problem for Propositional Dynamic Logic with Shuffle ($PDL^{||}$). While traditional model checking asks if a specific formula holds in a system, synthesis seeks to find any formula from a candidate set that is true. The authors demonstrate that while the general problem is undecidable due to the complexity of interleaved executions, imposing specific constraints on input grammars or system structures yields a range of decidable complexities. This work provides a formal bridge between logic synthesis, hierarchical planning, and security analysis.

Introduction: From Verification to Synthesis

In traditional formal verification, the goal is model checking: given a system $\mathcal{S}$ and a formula $\phi$, does $\mathcal{S} \models \phi$? This paper shifts the perspective to the formula-synthesis problem. Given a potentially infinite set of candidate formulas (defined by a grammar) and a system model, the task is to determine if there exists at least one formula in the set that is true for the system.

The logic of choice is $PDL^{||}$, an extension of Propositional Dynamic Logic (PDL) that incorporates a shuffle operator ($||$). This operator is essential for modeling concurrency, as it allows for reasoning about interleaved executions of programs. However, this expressive power comes at a cost: the shuffle operator significantly complicates the logic's semantics, often leading to infinite state spaces even within finite systems.

Methods and Theoretical Framework

The authors formalize the set of candidate formulas using regular term-grammars. These are context-free grammars designed to generate trees (logical formulas) rather than simple strings. To map the complexity landscape of the synthesis problem, the authors employ several key techniques:

  • Reductions for Undecidability: The general problem is proven undecidable by reducing it to the intersection problem for context-free word grammars.
  • Master Grammar Construction: For decidable fragments, the authors develop a method to construct a "master grammar" that generates all formulas true in a given transition system. The synthesis problem then reduces to checking the non-emptiness of the intersection between this master grammar and the user-provided input grammar.
  • Structural and Grammatical Constraints: The research explores how complexity shifts when the transition system is a Directed Acyclic Graph (DAG) or when the grammar is restricted (e.g., linear or non-recursive).
Figure 1: A transition system used to model interleaved executions and prove undecidability in PDL with shuffle.

Key Insights: The Complexity of Shuffle

The primary "villain" in this landscape is the shuffle operator. In standard PDL, the set of possible program executions between two states is essentially regular and can be captured by finite-state automata. The shuffle operator breaks this regularity, creating interleavings that require more powerful formalisms, which is the primary driver of undecidability.

However, the paper identifies a clear hierarchy of complexity based on these constraints:

  • General $PDL^{||}$: Undecidable (recursively enumerable complete).
  • Standard PDL (no shuffle): EXPTIME-complete.
  • DAG-like Systems: 2-EXPTIME.
  • Linear Grammars: PSPACE-complete.
  • Non-recursive Grammars: NP-complete to EXPSPACE.

Applications and Future Work

Beyond theoretical logic, formula synthesis serves as a natural abstraction for Hierarchical Task Networks (HTN). In HTN planning, complex tasks are decomposed into simpler ones via rules that are mathematically equivalent to the production rules in the authors' term-grammars. This framework also has potential in security attack-tree synthesis, where one might want to synthesize a logical description of a successful exploit path.

Future research directions include closing the gap in lower bounds for DAG-like systems and extending the framework to Game Logic. The latter would enable synthesis in adversarial environments, such as modeling a hacker actively working against a system's security protocols. Additionally, moving from explicit transition systems to symbolic representations remains a significant challenge for practical scalability.

Summary updated

BibTeX
@inproceedings{pinchinat2022formula,
  author = {Sophie Pinchinat and Sasha Rubin and François Schwarzentruber},
  title = {{Formula Synthesis in Propositional Dynamic Logic with Shuffle}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21227},
}
Figure