Report Number: CS-TR-88-1199
Institution: Stanford University, Department of Computer Science
Title: Projections of Vector Addition System Reachability Sets are
Author: Buning, H. K.
Author: Lettman, T.
Author: Mayr, E. W.
Date: March 1988
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".