Trace inclusion for one-counter nets revisited

DOI10.1007/978-3-319-11439-2_12MaRDI QIDQ3447702zbMATH OpenOpenAlexFDO

Authors Piotr Hofman, Patrick Totzke

Publication date 28 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-11439-2_12

Mathematics Subject Classification ID

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

Recommendations

• Trace inclusion for one-counter nets revisited
• Decidability of weak simulation on one-counter nets
• Simulation problems over one-counter nets
• Simulation over one-counter nets is PSPACE-complete
• One-counter automata with counter observability

Cites work

• Decidability of weak simulation on one-counter nets
• Deterministic one-counter automata
• Equivalence of deterministic one-counter automata is NL-complete
• Equivalences of Pushdown Systems Are Hard
• scientific article; zbMATH DE number 1232245 (Why is no real title available?)
• scientific article; zbMATH DE number 1304996 (Why is no real title available?)
• scientific article; zbMATH DE number 1500527 (Why is no real title available?)
• scientific article; zbMATH DE number 2086674 (Why is no real title available?)
• LTL with the freeze quantifier and register automata
• Petri nets and regular processes
• Simulation over one-counter nets is PSPACE-complete
• Trace inclusion for one-counter nets revisited
• Undecidability of bisimilarity for Petri nets and some related problems

Cited in

(10)

• Trace inclusion for one-counter nets revisited
• Complexity hierarchies beyond elementary
• Trace inclusion for one-counter nets revisited
• One-counter automata with counter observability
• Coverability, termination, and finiteness in recursive Petri nets
• Universality Problem for Unambiguous VASS
• On history-deterministic one-counter nets
• Dimension-minimality and primality of counter nets
• Language inclusion for boundedly-ambiguous vector addition systems is decidable
• Two-way one-counter nets revisited

This page was built for publication: Trace inclusion for one-counter nets revisited

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