Reachability in Succinct and Parametric One-Counter Automata

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

Mathematics Subject Classification ID

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