Shortest paths in reachability graphs

Jörg Desel; Javier Esparza

doi:10.1007/3-540-56863-8_49

Shortest paths in reachability graphs

Jörg Desel, Javier Esparza

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

We prove the following property for 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
Title of host publication	Application and Theory of Petri Nets 1993 - 14th International Conference, Proceedings
Editors	Marco Ajmone Marsan
Publisher	Springer Verlag
Pages	224-241
Number of pages	18
ISBN (Print)	9783540568636
DOIs	https://doi.org/10.1007/3-540-56863-8_49
State	Published - 1993
Externally published	Yes
Event	14th International Conference on Application and Theory of Petri Nets, 1993 - Chicago, United States Duration: 21 Jun 1993 → 25 Jun 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	691 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Application and Theory of Petri Nets, 1993
Country/Territory	United States
City	Chicago
Period	21/06/93 → 25/06/93

Access to Document

10.1007/3-540-56863-8_49

Cite this

Desel, J., & Esparza, J. (1993). Shortest paths in reachability graphs. In M. Ajmone Marsan (Ed.), Application and Theory of Petri Nets 1993 - 14th International Conference, Proceedings (pp. 224-241). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 691 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56863-8_49

@inproceedings{f3bc0d4073004a369ddb72098b1ef44c,

title = "Shortest paths in reachability graphs",

abstract = "We prove the following property for 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",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 14th International Conference on Application and Theory of Petri Nets, 1993 ; Conference date: 21-06-1993 Through 25-06-1993",

year = "1993",

doi = "10.1007/3-540-56863-8_49",

language = "English",

isbn = "9783540568636",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "224--241",

editor = "{ Ajmone Marsan}, Marco",

booktitle = "Application and Theory of Petri Nets 1993 - 14th International Conference, Proceedings",

}

Desel, J & Esparza, J 1993, Shortest paths in reachability graphs. in M Ajmone Marsan (ed.), Application and Theory of Petri Nets 1993 - 14th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 691 LNCS, Springer Verlag, pp. 224-241, 14th International Conference on Application and Theory of Petri Nets, 1993, Chicago, United States, 21/06/93. https://doi.org/10.1007/3-540-56863-8_49

Shortest paths in reachability graphs. / Desel, Jörg; Esparza, Javier.
Application and Theory of Petri Nets 1993 - 14th International Conference, Proceedings. ed. / Marco Ajmone Marsan. Springer Verlag, 1993. p. 224-241 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 691 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Shortest paths in reachability graphs

AU - Desel, Jörg

AU - Esparza, Javier

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - We prove the following property for 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 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=0012796557&partnerID=8YFLogxK

U2 - 10.1007/3-540-56863-8_49

DO - 10.1007/3-540-56863-8_49

M3 - Conference contribution

AN - SCOPUS:0012796557

SN - 9783540568636

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 224

EP - 241

BT - Application and Theory of Petri Nets 1993 - 14th International Conference, Proceedings

A2 - Ajmone Marsan, Marco

PB - Springer Verlag

T2 - 14th International Conference on Application and Theory of Petri Nets, 1993

Y2 - 21 June 1993 through 25 June 1993

ER -

Desel J, Esparza J. Shortest paths in reachability graphs. In Ajmone Marsan M, editor, Application and Theory of Petri Nets 1993 - 14th International Conference, Proceedings. Springer Verlag. 1993. p. 224-241. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-56863-8_49

Shortest paths in reachability graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this