Projections of vector addition system reachability sets are semilinear

Hans Kleine Büning, Theodor Lettmann, Ernst W. Mayr

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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".

Original languageEnglish
Pages (from-to)343-350
Number of pages8
JournalTheoretical Computer Science
Volume64
Issue number3
DOIs
StatePublished - 29 May 1989
Externally publishedYes

Fingerprint

Dive into the research topics of 'Projections of vector addition system reachability sets are semilinear'. Together they form a unique fingerprint.

Cite this