Projections of vector addition system reachability sets are semilinear

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

doi:10.1016/0304-3975(89)90055-8

Projections of vector addition system reachability sets are semilinear

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

Research output: Contribution to journal › Article › peer-review

6 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 language	English
Pages (from-to)	343-350
Number of pages	8
Journal	Theoretical Computer Science
Volume	64
Issue number	3
DOIs	https://doi.org/10.1016/0304-3975(89)90055-8
State	Published - 29 May 1989
Externally published	Yes

Access to Document

10.1016/0304-3975(89)90055-8

Cite this

@article{459e2552d9a843c3907f26647a6be516,

title = "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{"}.",

author = "{Kleine B{\"u}ning}, Hans and Theodor Lettmann and Mayr, {Ernst W.}",

year = "1989",

month = may,

day = "29",

doi = "10.1016/0304-3975(89)90055-8",

language = "English",

volume = "64",

pages = "343--350",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Projections of vector addition system reachability sets are semilinear

AU - Kleine Büning, Hans

AU - Lettmann, Theodor

AU - Mayr, Ernst W.

PY - 1989/5/29

Y1 - 1989/5/29

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

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

UR - http://www.scopus.com/inward/record.url?scp=0024663680&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(89)90055-8

DO - 10.1016/0304-3975(89)90055-8

M3 - Article

AN - SCOPUS:0024663680

SN - 0304-3975

VL - 64

SP - 343

EP - 350

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

Projections of vector addition system reachability sets are semilinear

Abstract

Access to Document

Other files and links

Fingerprint

Cite this