Skip to Main content Skip to Navigation
New interface
Journal articles

Efficiently Deciding µ-calculus with Converse over Finite Trees

Pierre Genevès 1 Nabil Layaïda 1 Alan Schmitt 2 Nils Gesbert 1 
1 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 CELTIQUE - Software certification with semantic analysis
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : We present a sound and complete satisfiability-testing algorithm and its effective implementation for an alternation-free modal µ-calculus with converse, where formulas are cycle-free and are interpreted over finite ordered trees. The time complexity of the satisfiability-testing algorithm is 2^O(n) in terms of formula size n. The algorithm is implemented using symbolic techniques (BDD). We present crucial implementation techniques and heuristics that we used to make the algorithm as fast as possible in practice. Our implementation is available online, and can be used to solve logical formulas of significant size and practical value. We illustrate this in the setting of XML trees.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Tyrex Equipe Connect in order to contact the contributor
Submitted on : Friday, January 30, 2015 - 3:28:14 PM
Last modification on : Monday, July 25, 2022 - 3:28:01 AM
Long-term archiving on: : Saturday, April 15, 2017 - 11:40:17 PM


Files produced by the author(s)





Pierre Genevès, Nabil Layaïda, Alan Schmitt, Nils Gesbert. Efficiently Deciding µ-calculus with Converse over Finite Trees. ACM Transactions on Computational Logic, 2015, 16 (2), pp.41. ⟨10.1145/2724712⟩. ⟨hal-00868722v5⟩



Record views


Files downloads