Simulation Problems Over One-Counter Nets

Hofman, Piotr, Lasota, Slawomir, Mayr, Richard and Totzke, Patrick ORCID: 0000-0001-5274-8190 (2016) Simulation Problems Over One-Counter Nets. Logical Methods in Computer Science, 12 (1). p. 1.

Access the full-text of this item by clicking on the Open Access link.

Text 1602.00476.pdf - Published version Download (648kB)

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.

Item Type:	Article
Additional Information:	timestamp: Mon, 13 Aug 2018 01:00:00 +0200 biburl: https://dblp.org/rec/bib/journals/corr/HofmanLMT16 bibsource: dblp computer science bibliography, https://dblp.org
Uncontrolled Keywords:	Computer Science, Logic in Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	21 Jan 2019 15:27
Last Modified:	20 Apr 2023 10:28
DOI:	10.2168/LMCS-12(1:6)2016
Open Access URL:	https://lmcs.episciences.org/1629
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3031037