Hofman, Piotr and Lasota, Slawomir and Mayr, Richard and Totzke, Patrick - Simulation Problems Over One-Counter Nets

lmcs:1629 - Logical Methods in Computer Science, March 14, 2016, Volume 12, Issue 1
Simulation Problems Over One-Counter Nets

Authors: Hofman, Piotr and Lasota, Slawomir and Mayr, Richard and Totzke, Patrick

One-counter nets (OCN) are finite automata equipped with a counter that can store non-negative integer values, and that cannot be tested for zero. Equivalently, these are exactly 1-dimensional vector addition systems with states. We show that both strong and weak simulation preorder on OCN are PSPACE-complete.


Source : oai:arXiv.org:1602.00476
DOI : 10.2168/LMCS-12(1:6)2016
Volume: Volume 12, Issue 1
Published on: March 14, 2016
Submitted on: June 17, 2015
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 115 times.
This article's PDF has been downloaded 34 times.