Existence of home states in Petri nets is decidable

Eike Best; Javier Esparza

doi:10.1016/j.ipl.2016.01.011

Existence of home states in Petri nets is decidable

Eike Best, Javier Esparza

Informatics 7 - Chair of Theoretical Computer Science

Universität Oldenburg

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

17 Scopus citations

Abstract

We show that the problem whether a given Petri net has a home state (a marking reachable from every reachable marking) is decidable, and at least as hard as the reachability problem.

Original language	English
Pages (from-to)	423-427
Number of pages	5
Journal	Information Processing Letters
Volume	116
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2016.01.011
State	Published - 1 Jun 2016

Keywords

Concurrency
Home states
Petri nets
Theory of computation

Access to Document

10.1016/j.ipl.2016.01.011

Cite this

@article{510547a18dac404c8d128dd90f154a4c,

title = "Existence of home states in Petri nets is decidable",

abstract = "We show that the problem whether a given Petri net has a home state (a marking reachable from every reachable marking) is decidable, and at least as hard as the reachability problem.",

keywords = "Concurrency, Home states, Petri nets, Theory of computation",

author = "Eike Best and Javier Esparza",

year = "2016",

month = jun,

day = "1",

doi = "10.1016/j.ipl.2016.01.011",

language = "English",

volume = "116",

pages = "423--427",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Existence of home states in Petri nets is decidable

AU - Best, Eike

AU - Esparza, Javier

PY - 2016/6/1

Y1 - 2016/6/1

N2 - We show that the problem whether a given Petri net has a home state (a marking reachable from every reachable marking) is decidable, and at least as hard as the reachability problem.

AB - We show that the problem whether a given Petri net has a home state (a marking reachable from every reachable marking) is decidable, and at least as hard as the reachability problem.

KW - Concurrency

KW - Home states

KW - Petri nets

KW - Theory of computation

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

U2 - 10.1016/j.ipl.2016.01.011

DO - 10.1016/j.ipl.2016.01.011

M3 - Article

AN - SCOPUS:84956600167

SN - 0020-0190

VL - 116

SP - 423

EP - 427

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Existence of home states in Petri nets is decidable

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this