Model-Checking CTL* over Flat Presburger Counter Systems

Stéphane Demri, Alain Finkel, Valentin Goranko, Govert van Drimmelen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This paper studies model-checking of fragments and extensions of CTL* on infinite- state counter systems, where the states are vectors of integers and the transitions are determined by means of relations definable within Presburger arithmetic. In general, reachability properties of counter systems are undecidable, but we have identified a natural class of admissible counter systems (ACS) for which we show that the quantification over paths in CTL* can be simulated by quantification over tuples of natural numbers, eventually allowing translation of the whole Presburger-CTL* into Presburger arithmetic, thereby enabling effective model checking. We provide evidence that our results are close to optimal with respect to the class of counter systems described above.
    Original languageEnglish
    JournalJournal of Applied Non-Classical Logics
    Volume20
    Issue number4
    Pages (from-to)313-344
    ISSN1166-3081
    DOIs
    Publication statusPublished - 2010

    Keywords

    • model-checking, infinite-state transition systems, Presburger arithmetic, CTL* , counter systems

    Fingerprint Dive into the research topics of 'Model-Checking CTL* over Flat Presburger Counter Systems'. Together they form a unique fingerprint.

    Cite this