2013/10/23 by Piotr Hofman, Hofman, Piotr, Sławomir Lasota +6
Computer Science · Decision Sciences · #68Q45 #D.2.4 #F.1.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Simulation Techniques and Applications #acm:68Q45 #cs.FL #msc:68Q45
paper · pdf · doi:10.48550/arxiv.1310.6303
Extended version of material presented at the FST&TCS 2013 conference. 22 pages
arxiv created 2013/10/23 · openalex publication_date 2013/10/23 · arxiv updated 2013/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One-counter nets (OCN) are Petri nets with exactly one unbounded place. They are equivalent to a subclass of one-counter automata with just a weak test for zero. Unlike many other semantic equivalences, strong and weak simulation preorder are decidable for OCN, but the computational complexity was an open problem. We show that both strong and weak simulation preorder on OCN are PSPACE-complete.