Reachability in Succinct and Parametric One-Counter Automata
From MaRDI portal
Publication:3184686
DOI10.1007/978-3-642-04081-8_25zbMath1254.68134OpenAlexW1532209667MaRDI QIDQ3184686
Joël Ouaknine, Christoph Haase, Stephan Kreutzer, James Worrell
Publication date: 22 October 2009
Published in: CONCUR 2009 - Concurrency Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-04081-8_25
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (21)
Countdown games, and simulation on (succinct) one-counter nets ⋮ Equivalence between model-checking flat counter systems and Presburger arithmetic ⋮ Context-free commutative grammars with integer counters and resets ⋮ Bisimulation equivalence and regularity for real-time one-counter automata ⋮ Unnamed Item ⋮ Reachability games with relaxed energy constraints ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Unnamed Item ⋮ Small vertex cover makes Petri net coverability and boundedness easier ⋮ Dynamic Complexity of the Dyck Reachability ⋮ On parametric timed automata and one-counter machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States ⋮ Unnamed Item ⋮ The Complexity of Flat Freeze LTL ⋮ Taming past LTL and flat counter systems ⋮ Reachability in two-clock timed automata is PSPACE-complete ⋮ Continuous One-counter Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- On the solvability of a class of Diophantine equations and applications
- On two-way FA with monotonic counters and quadratic Diophantine equations
- DP lower bounds for equivalence-checking and model-checking of one-counter automata
- The Effects of Bounding Syntactic Resources on Presburger LTL
- The Diophantine Problem for Addition and Divisibility
- Parametric real-time reasoning
- Automated Technology for Verification and Analysis
- Term Rewriting and Applications
- Programs with Lists Are Counter Automata
- Flat Parametric Counter Automata
This page was built for publication: Reachability in Succinct and Parametric One-Counter Automata
