Shortest paths in reachability graphs

Jörg Desel; Javier Esparza

doi:10.1006/jcss.1995.1070

Shortest paths in reachability graphs

Jörg Desel, Javier Esparza

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

6 Scopus citations

Abstract

We prove the following property for safe marked graphs, safe conflict-free Petri nets, and live and safe extended free-choice Petri nets: Given two markings M₁, M₂ of the reachability graph, if some path leads from M₁ to M₂. then some path of polynomial length in the number of transitions of the net leads from M₁ to M₂.

Original language	English
Pages (from-to)	314-323
Number of pages	10
Journal	Journal of Computer and System Sciences
Volume	51
Issue number	2
DOIs	https://doi.org/10.1006/jcss.1995.1070
State	Published - Oct 1995
Externally published	Yes

Access to Document

10.1006/jcss.1995.1070

Cite this

@article{69c6234754e04613ac28ee18c729117f,

title = "Shortest paths in reachability graphs",

abstract = "We prove the following property for safe marked graphs, safe conflict-free Petri nets, and live and safe extended free-choice Petri nets: Given two markings M1, M2 of the reachability graph, if some path leads from M1 to M2. then some path of polynomial length in the number of transitions of the net leads from M1 to M2.",

author = "J{\"o}rg Desel and Javier Esparza",

year = "1995",

month = oct,

doi = "10.1006/jcss.1995.1070",

language = "English",

volume = "51",

pages = "314--323",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Shortest paths in reachability graphs

AU - Desel, Jörg

AU - Esparza, Javier

PY - 1995/10

Y1 - 1995/10

N2 - We prove the following property for safe marked graphs, safe conflict-free Petri nets, and live and safe extended free-choice Petri nets: Given two markings M1, M2 of the reachability graph, if some path leads from M1 to M2. then some path of polynomial length in the number of transitions of the net leads from M1 to M2.

AB - We prove the following property for safe marked graphs, safe conflict-free Petri nets, and live and safe extended free-choice Petri nets: Given two markings M1, M2 of the reachability graph, if some path leads from M1 to M2. then some path of polynomial length in the number of transitions of the net leads from M1 to M2.

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

U2 - 10.1006/jcss.1995.1070

DO - 10.1006/jcss.1995.1070

M3 - Article

AN - SCOPUS:0029394220

SN - 0022-0000

VL - 51

SP - 314

EP - 323

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Shortest paths in reachability graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this