TY - UNPB

T1 - On the size of disjunctive formulas in the μ-calculus

AU - Kupke, Clemens

AU - Marti, Johannes

AU - Venema, Yde

N1 - Paper included in the conference proceedings, as available via arXiv.org: Proceedings 12th International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2021) - https://arxiv.org/abs/2109.07798

PY - 2021/9/17

Y1 - 2021/9/17

N2 - A key result in the theory of the modal mu-calculus is the disjunctive normal form theorem by Janin & Walukiewicz, stating that every mu-calculus formula is semantically equivalent to a so-called disjunctive formula. These disjunctive formulas have good computational properties and play a pivotal role in the theory of the modal mu-calculus. It is therefore an interesting question what the best normalisation procedure is for rewriting a formula into an equivalent disjunctive formula of minimal size. The best constructions that are known from the literature are automata-theoretic in nature and consist of a guarded transformation, i.e., the constructing of an equivalent guarded alternating automaton from a mu-calculus formula, followed by a Simulation Theorem stating that any such alternating automaton can be transformed into an equivalent non-deterministic one. Both of these transformations are exponential constructions, making the best normalisation procedure doubly exponential. Our key contribution presented here shows that the two parts of the normalisation procedure can be integrated, leading to a procedure that is single-exponential in the closure size of the formula.

AB - A key result in the theory of the modal mu-calculus is the disjunctive normal form theorem by Janin & Walukiewicz, stating that every mu-calculus formula is semantically equivalent to a so-called disjunctive formula. These disjunctive formulas have good computational properties and play a pivotal role in the theory of the modal mu-calculus. It is therefore an interesting question what the best normalisation procedure is for rewriting a formula into an equivalent disjunctive formula of minimal size. The best constructions that are known from the literature are automata-theoretic in nature and consist of a guarded transformation, i.e., the constructing of an equivalent guarded alternating automaton from a mu-calculus formula, followed by a Simulation Theorem stating that any such alternating automaton can be transformed into an equivalent non-deterministic one. Both of these transformations are exponential constructions, making the best normalisation procedure doubly exponential. Our key contribution presented here shows that the two parts of the normalisation procedure can be integrated, leading to a procedure that is single-exponential in the closure size of the formula.

KW - disjunctive formulas

KW - μ-calculus

KW - GandALF 2021

UR - https://arxiv.org/abs/2109.07798

U2 - 10.4204/EPTCS.346.19

DO - 10.4204/EPTCS.346.19

M3 - Working paper

T3 - EPTCS

SP - 291

EP - 307

BT - On the size of disjunctive formulas in the μ-calculus

CY - Ithaca, NY

ER -