文章基本信息

标题：Simulation Over One-counter Nets is PSPACE-Complete
本地全文：下载
作者：Piotr Hofman ; Slawomir Lasota ; Richard Mayr 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：24
页码：515-526
DOI：10.4230/LIPIcs.FSTTCS.2013.515
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Simulation preorder; one-counter nets; complexity