Projections of Vector Addition System Reachability Sets Are Semilinear
Abstract
The reachability sets of Vector Addition Systems of dimension six or more can be non-semilinear. This may be one reason why the inclusion problem (as well as the equality problem) for reachability sets of vector addition systems in general is undecidable, even though the reachability problem itself is known to be decidable. We show that any one-dimensional projection of the reachability set of an arbitrary vector addition system is semilinear, and hence simple.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 29, 1988
- Accession Number
- ADA205914
Entities
People
- E. W. Mayr
- H. K. Buening
- T. Lettmann
Organizations
- Stanford University