From strong to exact Petri net computers

Dmitry A. Zaitsev, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Petri net paradigm of computing is concerned discussing basic types of Petri net computers and their relations. We developed a technique of parametric specification of Petri nets, built of a few connected components which are repeated depending on a parameter or a set of parameters, and composition of software to generate automatically the corresponding models in a vivid graphical form. We construct explicitly a Petri net that is a strong computer of double exponent after R.J. Lipton. Its nondeterministic computation is represented by a Petri net reachability graph to which a successful branch belongs. Then we minimise and transform the net to obtain twice smaller construct than the original one. Moreover, the obtained net possesses such a marvellous property that addingto it four priority arcs makes it an exact (deterministic) computer having a single firable sequence only. Same as the Lipton’s net, the minimized net allows the proof that the Petri net reachability problem is exponential in space. Besides, it represents an example when simple transformations allow guessing the successful branch of a nondeterministic computation. The practical significance of the approach in applications consists in a state-of-art heuristic technique of solving some NP problems in polynomial time.

Original languageEnglish (US)
Pages (from-to)167-186
Number of pages20
JournalInternational Journal of Parallel, Emergent and Distributed Systems
Volume37
Issue number2
DOIs
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications

Keywords

  • Petri net
  • double exponent
  • exact computer
  • strong computer

Fingerprint

Dive into the research topics of 'From strong to exact Petri net computers'. Together they form a unique fingerprint.

Cite this