2013/02/15 by Dmitry A. Zaitsev · 1 citation
Computer Science · Mathematics · #Petri Nets in System Modeling #Formal Methods in Verification #Distributed systems and fault tolerance #Petri net #Computer science #Encoding (memory) #Net (polyhedron) #Turing machine #Class (philosophy) #Time complexity #Stochastic Petri net #Algorithm #Exponential function #Theoretical computer science #Discrete mathematics #Sequence (biology) #Parallel computing #Mathematics #Artificial intelligence #Computation #Geometry
paper · doi:10.1109/tsmc.2012.2237549
openalex publication_date 2013/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
A universal Petri net with 14 places, 42 transitions, and 218 arcs was built in the class of deterministic inhibitor Petri nets (DIPNs); it is based on the minimal Turing machine (TM) of Woods and Neary with 6 states, 4 symbols, and 23 instructions, directly simulated by a Petri net. Several techniques were developed, including bi-tag system (BTS) construction on a DIPN, special encoding of TM tape by two stacks, and concise subnets that implement arithmetic encoding operations. The simulation using the BTS has cubic time and linear space complexity, while the resulting universal net runs in exponential time and quadratic space with respect to the target net transitions' firing sequence length. The technique is applicable for simulating any TM by the Petri net.