Report Number: CS-TR-88-1199
Institution: Stanford University, Department of Computer Science
Title: Projections of Vector Addition System Reachability Sets are Semilinear
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".
http://i.stanford.edu/pub/cstr/reports/cs/tr/88/1199/CS-TR-88-1199.pdf