2013/12/16 by Sergiu Ivanov, Ivanov, Sergiu, Elisabeth Pelz +3
Business, Management and Accounting · Computer Science · #68Q05 #68Q10 #68Q17 #Business Process Modeling and Analysis #Computational Complexity (cs.CC) #Computer science #Discrete Mathematics (cs.DM) #F.1.1 #F.1.3 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Petri Nets in System Modeling #Petri net #Programming language #acm:68Q05 #acm:68Q10 #acm:68Q17 #cs.CC #cs.DM #cs.FL #msc:68Q05 #msc:68Q10 #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1312.4414
arxiv created 2013/12/16 · openalex publication_date 2013/12/16 · arxiv updated 2013/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the problem of construction of small-size universal Petri nets with inhibitor arcs. We consider four descriptional complexity parameters: the number of places, transitions, inhibitor arcs, and the maximal degree of a transition, each of which we try to minimize. We give six constructions having the following values of parameters (listed in the above order): (30,34,13,3), (14, 31, 51, 8), (11, 31, 79, 11), (21,25,13,5), (67, 64, 8, 3), (58, 55, 8, 5) that improve the few known results on this topic. Our investigation also highlights several interesting trade-offs.