Simulation problems over one-counter nets

DOI10.2168/LMCS-12(1:6)2016MaRDI QIDQ2800968zbMATH OpenFDO

Authors Piotr Hofman, Sławomir Lasota, Patrick Totzke, Richard M. Mayr

Publication date 19 April 2016

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.00476

zbMATH Keywords

complexitysimulation preorderone-counter nets

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

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.

Recommendations

• Simulation over one-counter nets is PSPACE-complete
• Decidability of weak simulation on one-counter nets
• scientific article; zbMATH DE number 1500527
• scientific article; zbMATH DE number 1304996
• scientific article; zbMATH DE number 1490007

Cited in

(12)

• scientific article; zbMATH DE number 7559503 (Why is no real title available?)
• Simulation over one-counter nets is PSPACE-complete
• Trace inclusion for one-counter nets revisited
• Countdown games, and simulation on (succinct) one-counter nets
• A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
• Trace inclusion for one-counter nets revisited
• The complexity of flat freeze LTL
• The complexity of flat freeze LTL
• EXPSPACE-complete variant of countdown games, and simulation on succinct one-counter nets
• On history-deterministic one-counter nets
• Decidability of weak simulation on one-counter nets
• scientific article; zbMATH DE number 1696434 (Why is no real title available?)

This page was built for publication: Simulation problems over one-counter nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800968)