TR02-04 (2002) – Decidability and Complexity of Petri Net Problems

Olivia Oanea

Petri net theory plays a very important role in modeling and analysing parallel and distributed systems. It provides a simple mathematical structure, and basic propertiescan be cleanly analysed.The aim of this paper is to give an overviewon the basic decision problems in the theoryof Petri nets. We discuss both decidability and complexity aspects.We have also a contribution in the area ofhome markings. We prove thatthe home marking problem for inhibitor Petrinets is undecidable.

Bibtex

@TechReport{dcpnp,
  author = 	 {Olivia Oanea},
  title = 	 {Decidability and Complexity of Petri Net Problems},
  institution =  {University ``A.I.Cuza'' of Iac{s}i, Faculty of
Computer Science},
  year = 	 {2002},
  number = 	 {TR 02-04},
  note = 	 {URL:http://www.infoiasi.ro/~tr/tr.pl.cgi}
}