Title :
Petri Net Computers and Workflow Nets
Author :
Ţiplea, Ferucio L. ; Diaconu, Raluca A.
Author_Institution :
Dept. of Comput. Sci., Alexandru Ioan Cuza Univ. of Iasi, Iaşi, Romania
Abstract :
In this paper, a robust and as simple as possible concept of a Petri net (PN) computer is proposed. It has a similar structure and behavior to weak sound priority workflow nets. It is shown that all recursive functions are PN computable and, vice-versa, PN computable functions are recursive. This shows that the PN computers we have proposed have exactly the power of Turing machines. Complexity classes of PN computable functions are defined, and the relationship between them and similar complexity classes defined by counter machines is investigated. Finally, the close relationship between PN computers and weak sound (priority) workflow nets is investigated.
Keywords :
Petri nets; Turing machines; computability; computational complexity; recursive functions; PN computable functions; PN computer; Petri net computers; Turing machines; complexity classes; counter machines; recursive functions; weak-sound priority workflow nets; Complexity theory; Computational modeling; Computers; Inhibitors; Radiation detectors; Turing machines; Vectors; Complexity class; Petri net (PN); computable function; counter machine (CM); workflow net;
Journal_Title :
Systems, Man, and Cybernetics: Systems, IEEE Transactions on
DOI :
10.1109/TSMC.2014.2347933
