Precise fixpoint computation through strategy iteration

Thomas Gawlitza; Helmut Seidl

doi:10.1007/978-3-540-71316-6_21

Precise fixpoint computation through strategy iteration

Thomas Gawlitza, Helmut Seidl

Research output: Contribution to journal › Conference article › Research › peer-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 language	English
Book series	Lecture Notes in Computer Science
Volume	4421
Pages (from-to)	300-315
ISSN	0302-9743
DOIs	https://doi.org/10.1007/978-3-540-71316-6_21
Publication status	Published - 2007
Event	16th 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 2007 → 1 Apr 2007 Conference number: 16 http://rap.dsi.unifi.it/esop07/

Conference

Conference	16th European Symposium on Programming
Number	16
Country/Territory	Portugal
City	Braga
Period	24/03/2007 → 01/04/2007
Internet address	http://rap.dsi.unifi.it/esop07/

Bibliographical note

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

Access to Document

10.1007/978-3-540-71316-6_21

OpenUrl availability

Full text

Cite this

@inproceedings{86079e1b232b48fbb3d0039d9ac84643,

title = "Precise fixpoint computation through strategy iteration",

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.",

author = "Thomas Gawlitza and Helmut Seidl",

note = "ISBN: 978-3-540-71314-2 (Book in journal series) DOI: 10.1007/978-3-540-71316-6 (Book in journal series); 16th European Symposium on Programming : Held as Part of the Joint European Conferences on Theory and Practics of Software, ETAPS 2007, ESOP07 ; Conference date: 24-03-2007 Through 01-04-2007",

year = "2007",

doi = "10.1007/978-3-540-71316-6_21",

language = "English",

volume = "4421",

pages = "300--315",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

url = "http://rap.dsi.unifi.it/esop07/",

}

TY - GEN

T1 - Precise fixpoint computation through strategy iteration

AU - Gawlitza, Thomas

AU - Seidl, Helmut

N1 - Conference code: 16

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-71316-6_21

DO - 10.1007/978-3-540-71316-6_21

M3 - Conference article

SN - 0302-9743

VL - 4421

SP - 300

EP - 315

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 16th European Symposium on Programming

Y2 - 24 March 2007 through 1 April 2007

ER -

Precise fixpoint computation through strategy iteration

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this