AEfficiently Deciding µ-calculus with Converse over Finite Trees

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 fi-nite ordered trees. The time complexity of the satisfiability-testing algorithm is 2O(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 implemen-tation 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