# Symbolic Representation of Upwards Closed Sets

### Giorgio Delzanno and Jean-Francois Raskin

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-99-1075

1999

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1075.pdf

The reachability problem for a wide class of infinite-state systems is decidable when the initial and the final set of configurations are given as upwards closed sets. Traditional symbolic model checking methods suffer from the state explosion problem when applied to this class of verification problems.

We provide new data structures and algorithms for an efficient manipulation of upwards closed sets. These operations can be incorporated into model checking procedures for integer systems with infinite-states space. We report on experiments for verification problems of Vector Addition Systems.

BibTeX citation:

@techreport{Delzanno:CSD-99-1075, Author = {Delzanno, Giorgio and Raskin, Jean-Francois}, Title = {Symbolic Representation of Upwards Closed Sets}, Institution = {EECS Department, University of California, Berkeley}, Year = {1999}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/5715.html}, Number = {UCB/CSD-99-1075}, Abstract = {The reachability problem for a wide class of infinite-state systems is decidable when the initial and the final set of configurations are given as upwards closed sets. Traditional symbolic model checking methods suffer from the state explosion problem when applied to this class of verification problems. <p>We provide new data structures and algorithms for an efficient manipulation of upwards closed sets. These operations can be incorporated into model checking procedures for integer systems with infinite-states space. We report on experiments for verification problems of Vector Addition Systems.} }

EndNote citation:

%0 Report %A Delzanno, Giorgio %A Raskin, Jean-Francois %T Symbolic Representation of Upwards Closed Sets %I EECS Department, University of California, Berkeley %D 1999 %@ UCB/CSD-99-1075 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/5715.html %F Delzanno:CSD-99-1075