MONA Implementation Secrets

Nils Klarlund, Anders Møller, Michael Ignatieff Schwartzbach

    Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

    Abstract

    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
    Title of host publicationImplementation and Application of Automata : 5th International Conference, CIAA 2000 London, Ontario, Canada, July 24-25, 2000 Revised Papers
    EditorsSheng Yu, Andrei Paun
    Number of pages13
    PublisherSpringer
    Publication date2001
    Pages182-194
    ISBN (Print)3-540-42491-1
    DOIs
    Publication statusPublished - 2001
    EventInternational Conference on Implementation and Application of Automata. CIAA '00 - London, ON, Canada
    Duration: 24 Jul 200026 Jul 2000
    Conference number: 5

    Conference

    ConferenceInternational Conference on Implementation and Application of Automata. CIAA '00
    Number5
    Country/TerritoryCanada
    CityLondon, ON
    Period24/07/200026/07/2000
    SeriesLecture Notes in Computer Science
    Volume2088
    ISSN0302-9743

    Fingerprint

    Dive into the research topics of 'MONA Implementation Secrets'. Together they form a unique fingerprint.

    Cite this