Simulation Problems Over One-Counter Nets

Richard Mayr; Slawomir Lasota; Piotr Hofman; Patrick Totzke

doi:10.2168/LMCS-12(1:6)2016

Simulation Problems Over One-Counter Nets

Richard Mayr, Slawomir Lasota, Piotr Hofman, Patrick Totzke

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

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.

Original language	English
Article number	6
Pages (from-to)	1-46
Number of pages	46
Journal	Logical Methods in Computer Science
Volume	12
Issue number	1
DOIs	https://doi.org/10.2168/LMCS-12(1:6)2016
Publication status	Published - 14 Mar 2016

Keywords / Materials (for Non-textual outputs)

Simulation preorder; one-counter nets; complexity

Access to Document

10.2168/LMCS-12(1:6)2016

1602.00476Final published version, 633 KBLicence: Creative Commons: Attribution No Derivatives (CC-BY-ND)

http://www.lmcs-online.org/ojs/viewarticle.php?id=1865Licence: Creative Commons: Attribution No Derivatives (CC-BY-ND)

Energy Efficient Control
Mayr, R.
EPSRC
1/09/15 → 31/08/19
Project: Research

Cite this

@article{2703d52063794784b3d5cb999f157403,

title = "Simulation Problems Over One-Counter Nets",

abstract = "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.",

keywords = "Simulation preorder; one-counter nets; complexity",

author = "Richard Mayr and Slawomir Lasota and Piotr Hofman and Patrick Totzke",

year = "2016",

month = mar,

day = "14",

doi = "10.2168/LMCS-12(1:6)2016",

language = "English",

volume = "12",

pages = "1--46",

journal = "Logical Methods in Computer Science",

issn = "1860-5974",

publisher = "Technischen Universitat Braunschweig",

number = "1",

}

TY - JOUR

T1 - Simulation Problems Over One-Counter Nets

AU - Mayr, Richard

AU - Lasota, Slawomir

AU - Hofman, Piotr

AU - Totzke, Patrick

PY - 2016/3/14

Y1 - 2016/3/14

N2 - 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.

AB - 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.

KW - Simulation preorder; one-counter nets; complexity

U2 - 10.2168/LMCS-12(1:6)2016

DO - 10.2168/LMCS-12(1:6)2016

M3 - Article

SN - 1860-5974

VL - 12

SP - 1

EP - 46

JO - Logical Methods in Computer Science

JF - Logical Methods in Computer Science

IS - 1

M1 - 6

ER -

Simulation Problems Over One-Counter Nets

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

Energy Efficient Control

Cite this