Precise fixpoint computation through strategy iteration

Thomas Gawlitza, Helmut Seidl

    Research output: Contribution to journalConference articleResearchpeer-review

    Abstract

    We present a practical algorithm for computing least solutions of systems of equations over the integers with addition, multiplication with positive constants, maximum and minimum. The algorithm is based on strategy iteration. Its run-time (w.r.t. the uniform cost measure) is independent of the sizes of occurring numbers. We apply our technique to solve systems of interval equations. In particular, we show how arbitrary intersections as well as full interval multiplication in interval equations can be dealt with precisely.
    Original languageEnglish
    Book seriesLecture Notes in Computer Science
    Volume4421
    Pages (from-to)300-315
    ISSN0302-9743
    DOIs
    Publication statusPublished - 2007
    Event16th European Symposium on Programming : Held as Part of the Joint European Conferences on Theory and Practics of Software, ETAPS 2007 - Braga, Portugal
    Duration: 24 Mar 20071 Apr 2007
    Conference number: 16
    http://rap.dsi.unifi.it/esop07/

    Conference

    Conference16th European Symposium on Programming
    Number16
    CountryPortugal
    CityBraga
    Period24/03/200701/04/2007
    Internet address

    Bibliographical note

    ISBN: 978-3-540-71314-2 (Book in journal series)
    DOI: 10.1007/978-3-540-71316-6 (Book in journal series)

    Fingerprint Dive into the research topics of 'Precise fixpoint computation through strategy iteration'. Together they form a unique fingerprint.

    Cite this