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.

    https://doi.org/10.2168/LMCS-12(1:6)2016
    Source: arXiv.org:1602.00476
    Volume: Volume 12, Issue 1
    Published on: March 14, 2016
    Submitted on: June 17, 2015
    Keywords: Computer Science - Logic in Computer Science
    Licence: arXiv.org - Non-exclusive license to distribute

    2 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 1834 times.
    This article's PDF has been downloaded 409 times.