Trace inclusion for one-counter nets revisited

DOI10.1016/j.tcs.2017.05.009zbMath1393.68118arXiv1404.5157OpenAlexW2616623755MaRDI QIDQ2636512

Patrick Totzke, Piotr Hofman

Publication date: 5 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

equivalence checkingvector addition systemscounter-automata

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ The Parametric Complexity of Lossy Counter Machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidability of bisimilarity for Petri nets and some related problems
• Deterministic one-counter automata
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Petri nets and regular processes
• LTL with the freeze quantifier and register automata
• Simulation Over One-counter Nets is PSPACE-Complete
• Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete
• Decidability of Weak Simulation on One-Counter Nets
• Automated Technology for Verification and Analysis
• Equivalence of deterministic one-counter automata is NL-complete

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