Simulation problems over one-counter nets

DOI10.2168/LMCS-12(1:6)2016zbMATH Open1448.68342arXiv1602.00476MaRDI QIDQ2800968FDOQ2800968

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)

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.

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

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

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)

Cited In (12)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)