A Decision Procedure for a Fragment of Linear Time Mu-Calculus

Yao Liu, Zhenhua Duan, Cong TianIJCAI 2016

Introduction

Automated planning and formal verification rely heavily on Linear Temporal Logic (LTL) to specify goals. While LTL is computationally efficient, it lacks the expressiveness to capture certain $\omega$-regular properties, such as complex periodic behaviors. Linear time $\mu$-calculus ($\nu TL$) offers the necessary expressiveness through fixpoint operators but suffers from significantly higher decision complexity ($2^{O(|\phi|^2 \log |\phi|)}$). This paper introduces $G_\mu$, a fragment of $\nu TL$ that bridges this gap by maintaining LTL's complexity ($2^{O(|\phi|)}$) while expanding its expressive power.

The $G_\mu$ Logic Fragment

The core contribution is the definition of the $G_\mu$ logic. The syntax follows the standard linear time $\mu$-calculus grammar but imposes a critical structural restriction: for any least fixpoint subformula ($\mu X.\phi$) and any conjunction ($\phi_1 \wedge \phi_2$), the fixpoint variable $X$ can only appear in one of the conjuncts. This restriction simplifies the unfolding of recursive formulas, preventing the exponential state explosion typically associated with nested fixpoints in conjunctions.

Methodology: Progression and Graphs

The decision procedure relies on two main constructs: Goal Progression Form (GPF) and the Goal Progression Form Graph (GPG).

Goal Progression Form (GPF)

GPF is a rewriting technique that decomposes a $G_\mu$ formula into a disjunction of terms, each separating requirements for the current state from those for the next state. Formally, $\varphi = \bigvee_{i=1}^k (\varphi_{p_i} \wedge \bigcirc \varphi_{f_i})$, where $\varphi_{p_i}$ is a propositional formula and $\varphi_{f_i}$ is the "future" formula.

Goal Progression Form Graph (GPG)

The GPG is a state-transition graph where nodes represent formulas and edges represent transitions between them. The authors provide an algorithm, GPFCON, to construct this graph iteratively.

Algorithm for constructing the Goal Progression Form Graph (GPG) from a $G_\mu$ formula.

A key feature of the GPG is the use of marks—sets of variables on edges that track which fixpoints are being unfolded. These marks are essential for the decision procedure to ensure that least fixpoints eventually terminate.

An example of a Goal Progression Form Graph (GPG) for a $G_\mu$ formula, showing nodes, transitions, and marks.

The decision procedure searches this graph for a $\nu$-path: an infinite path where no least fixpoint is unfolded infinitely. This search effectively checks the satisfiability of the goal.

Key Results and Complexity

The authors demonstrate that the decision procedure for $G_\mu$ has a complexity of $2^{O(|\phi|)}$, matching LTL. Despite this efficiency, $G_\mu$ is strictly more expressive than LTL, capable of specifying any property in the deterministic $\mu$-calculus ($D_\mu$) and handling complex periodic goals that fall outside LTL's scope.

Conclusion and Future Work

By restricting the interaction between least fixpoints and conjunctions, $G_\mu$ provides a powerful yet efficient alternative to LTL for automated planning. Future work includes implementing this procedure into a functional model checker and extending it to handle non-deterministic or partially observable environments.

Summary updated

BibTeX
@inproceedings{liu2016decision,
  author = {Yao Liu and Zhenhua Duan and Cong Tian},
  title = {{A Decision Procedure for a Fragment of Linear Time Mu-Calculus}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure