MONA Implementation Secrets

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Nils Klarlund, Denmark
  • Anders Møller
  • Michael Ignatieff Schwartzbach, Denmark
  • Department of Computer Science
The MONA tool provides an implementation of the decision procedures for the logics WS1S and WS2S. It has been used for numerous applications, and it is remarkably efficient in practice, even though it faces a theoretically non-elementary worst-case complexity. The implementation has matured over a period of six years. Compared to the first naive version, the present tool is faster by several orders of magnitude. This speedup is obtained from many different contributions working on all levels of the compilation and execution of formulas. We present a selection of implementation "secrets" that have been discovered and tested over the years, including formula reductions, DAGification, guided tree automata, three-valued logic, eager minimization, BDD-based automata representations, and cache-conscious data structures. We describe these techniques and quantify their respective effects by experimenting with separate versions of the MONA tool that in turn omit each of them.
Original languageEnglish
JournalInternational Journal of Foundations of Computer Science
Volume13
Issue4
Pages (from-to)571-586
Number of pages16
ISSN0129-0541
DOIs
Publication statusPublished - 2002

    Research areas

  • Monadic second-order logic, finite-state automata, the MONA tool

See relations at Aarhus University Citationformats

ID: 282316