Separability of reachability sets of vector addition systems

Abstract: Given two families of sets

m a t h c a l F

and

m a t h c a l G

, the

m a t h c a l F

separability problem for

m a t h c a l G

asks whether for two given sets

U, V i n m a t h c a l G

there exists a set

S i n m a t h c a l F

, such that

U

is included in

S

and

V

is disjoint with

S

. We consider two families of sets

m a t h c a l F

: modular sets

S s u b s e t e q m a t h b b N^{d}

, defined as unions of equivalence classes modulo some natural number

n i n m a t h b b N

, and unary sets. Our main result is decidability of modular and unary separability for the class

m a t h c a l G

of reachability sets of Vector Addition Systems, Petri Nets, Vector Addition Systems with States, and for sections thereof.

Recommendations

Cited in

(13)

This page was built for publication: Separability of reachability sets of vector addition systems