On the size of disjunctive formulas in the μcalculus
Kupke, Clemens and Marti, Johannes and Venema, Yde (2021) On the size of disjunctive formulas in the μcalculus. Preprint / Working Paper. arXiv.org, Ithaca, NY. (https://doi.org/10.4204/EPTCS.346.19)
Preview 
Text.
Filename: Kupke_etal_arXiv_2021_On_the_size_of_disjunctive_formulas_in_the_calculus.pdf
Preprint License: Strathprints license 1.0 Download (1MB) Preview 
Abstract
A key result in the theory of the modal mucalculus is the disjunctive normal form theorem by Janin & Walukiewicz, stating that every mucalculus formula is semantically equivalent to a socalled disjunctive formula. These disjunctive formulas have good computational properties and play a pivotal role in the theory of the modal mucalculus. 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 automatatheoretic in nature and consist of a guarded transformation, i.e., the constructing of an equivalent guarded alternating automaton from a mucalculus formula, followed by a Simulation Theorem stating that any such alternating automaton can be transformed into an equivalent nondeterministic 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 singleexponential in the closure size of the formula.


Item type: Monograph(Preprint / Working Paper) ID code: 81848 Dates: DateEvent17 September 2021Published17 September 2021SubmittedNotes: 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 Keywords: disjunctive formulas, μcalculus, GandALF 2021, Mathematics, Mathematics(all) Subjects: Science > Mathematics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 11 Aug 2022 16:02 Last modified: 12 Aug 2023 01:32 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/81848