TR02-02 (2002) – The Home Marking Problem and Some Related Concepts

R. Melinte, O. Oanea, I. Olga, F.L. Tiplea

In this paper we study the home marking problemfor Petri nets, and some related concepts to it like confluence, noetherianity, and state space inclusion. We show that the home marking problem for inhibitor Petri nets is undecidable. We relate then the existenceof home markings to confluence and noetherianity andprove that confluent and noetherian Petri nets havean unique home marking. Finally, we define some versions of the state space inclusion problem related to thehome marking and sub-marking problems, and discuss their decidability status.

Bibtex

@TechReport{hmpsrc,
  author = 	 {R. Melinte and O. Oanea and I. Olga and F.L. Tiplea},
  title = 	 {The Home Marking Problem and Some Related Concepts},
  institution =  {University ``A.I.Cuza'' of Iac{s}i, Faculty of
Computer Science},
  year = 	 {2002},
  number = 	 {TR 02-02},
  note = 	 {URL:http://www.infoiasi.ro/~tr/tr.pl.cgi}
}