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

lmcs:1629 - Logical Methods in Computer Science, March 14, 2016, Volume 12, Issue 1 - https://doi.org/10.2168/LMCS-12(1:6)2016
Simulation Problems Over One-Counter NetsArticle

Authors: Piotr Hofman ; Slawomir Lasota ; Richard Mayr ; Patrick Totzke ORCID

    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.


    Volume: Volume 12, Issue 1
    Published on: March 14, 2016
    Submitted on: June 17, 2015
    Keywords: Computer Science - Logic in Computer Science

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1336 times.
    This article's PDF has been downloaded 350 times.