More on Nonregular PDL: Finite Models and Fibonacci-Like Programs

David Harel, Eli SingermanInf. Comput 1996 · DOI

TL;DR

This paper investigates the decidability of propositional dynamic logic (PDL) when extended with nonregular programs. The authors show that adding certain nonregular programs, like those generating Fibonacci-like sequences, can lead to undecidable validity problems, while others might still retain decidability by violating the crucial "finite model property."

What Problem Does This Paper Address?

Propositional Dynamic Logic (PDL) is a powerful formalism for reasoning about programs. A key property that makes PDL decidable is the "small model property" (or finite model property, fmp), which guarantees that any satisfiable formula has a finite model. This property allows for decidability proofs using techniques like filtration. However, extending PDL with nonregular programs (which go beyond simple sequential, choice, and iteration constructs, akin to recursive procedures) can break this decidability.

The research community has been exploring the boundary between decidable and undecidable extensions of PDL by adding nonregular languages as new programs. While some extensions, like those involving context-free languages like $a^n b^n$, are decidable, others, like $a^n b^n a^n$, are highly undecidable. This paper focuses on two main questions:

  1. Finite Model Property: Under what conditions do one-letter nonregular extensions of PDL lose the finite model property? This is a step towards understanding decidability, as losing the fmp often implies undecidability.
  2. Decidability of Specific Cases: Can we establish the decidability status (or undecidability) for specific classes of nonregular programs, particularly those related to sequences like Fibonacci numbers?

Methods

The paper tackles these questions using a combination of theoretical tools:

  • Finite Model Property Violation: The authors introduce a general condition (Theorem 3.3) that is sufficient for a one-letter nonregular extension of PDL to violate the finite model property. This condition involves properties of the set of exponents generated by the program (e.g., for $a^S$, the set $S \subseteq \mathbb{N}$). The proof relies on constructing a specific type of infinite model that cannot be simulated by any finite model, thus demonstrating the absence of the fmp.
  • Undecidability Proofs: For Fibonacci-like sequences, the paper establishes $\Pi_1^1$-completeness for the validity problem. This is achieved by a complex reduction from a known undecidable tiling problem (recurring dominoes). The core idea is to encode the tiling problem's constraints into PDL formulas involving a Fibonacci-like program, such that the satisfiability of the PDL formula corresponds to the tileability of the grid. This reduction leverages a "grid-like property" of Fibonacci numbers.
  • Specific Program Classes: The paper analyzes various classes of one-letter nonregular programs, including polynomials, sums of primes, factorials, and linear recurrences, to see if they satisfy the condition for violating the fmp.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on logical properties and abstract program structures rather than empirical evaluation on datasets.

Key Insights and Ideas

  • The "Fibonacci Trap": Fibonacci-like sequences, despite their seemingly simple recursive definition, are powerful enough to encode complex computational problems. Adding them as programs to PDL leads to highly undecidable validity problems ($\Pi_1^1$-complete). This highlights how seemingly innocent mathematical sequences can have profound implications for logical systems.
  • A General Condition for Losing the FMP: The paper provides a concrete, albeit technical, condition (Theorem 3.3) that can be used to prove that many one-letter nonregular PDL extensions lack the finite model property. This is a valuable tool for researchers in the field.
  • Polynomials and Other Sequences Break FMP: The authors demonstrate that PDL extended with programs generating squares, cubes, general polynomials, sums of primes, and linear recurrences (including Fibonacci) all violate the finite model property. This suggests that a wide range of "natural" nonregular sequences can destabilize PDL's decidability.
  • Distinguishing Decidable vs. Undecidable: The paper implicitly underscores the delicate balance in PDL extensions. While some nonregular programs lead to undecidability, others might still be decidable, often requiring more sophisticated techniques than simple filtration. The focus on the fmp is a crucial intermediate step in this distinction.

Key Results

  • Violation of Finite Model Property: PDL extended with programs corresponding to squares ($a^{i^2}$), cubes ($a^{i^3}$), general polynomials, sums of primes, and linear recurrences (including Fibonacci) violates the finite model property.
  • $\Pi_1^1$-Completeness for Fibonacci Programs: The validity problem for PDL extended with any Fibonacci-like sequence ($f_{i+1} = f_i + f_{i-1}$) is $\Pi_1^1$-complete. This is a significant result, placing it at the higher end of the undecidability hierarchy.

Limitations and Future Work

  • Focus on One-Letter Extensions: The paper primarily focuses on one-letter nonregular programs. The behavior of multi-letter nonregular programs, while mentioned as being generally more complex, is not the main focus.
  • Decidability Status of Some Cases: While the paper shows that many specific one-letter extensions violate the fmp, it doesn't definitively prove undecidability for all of them. However, violating the fmp is a strong indicator of potential undecidability.
  • Future Work: The authors suggest that the techniques used here could be generalized to other classes of sequences and programs. Further investigation into the decidability of PDL with specific nonregular programs that do retain the fmp is also an open area. The paper also hints at the difficulty of characterizing precisely which nonregular extensions lead to undecidability.

Summary updated

BibTeX
@article{harel1996more,
  author = {David Harel and Eli Singerman},
  title = {{More on Nonregular PDL: Finite Models and Fibonacci-Like Programs}},
  journal = {Inf. Comput.},
  year = {1996},
  doi = {10.1006/inco.1996.0066},
}
Figure