Hardness results for coverability problem of well-structured pushdown systems

DOI10.1007/978-3-319-53733-7_32MaRDI QIDQ5739016zbMATH OpenOpenAlexFDO

Authors Chunmiao Li, Xiaojuan Cai

Publication date 1 June 2017

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-53733-7_32

zbMATH Keywords

automatacoverabilitylower boundspushdown systems

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) 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

• Well-structured pushdown systems
• Well-structured pushdown system: case of dense timed pushdown automata
• Hyper-Ackermannian bounds for pushdown vector addition systems
• On boundedness problems for pushdown vector addition systems
• Verification, Model Checking, and Abstract Interpretation

Cites work

• Algorithmic analysis of programs with well quasi-ordered domains.
• Analysis of recursively parallel programs
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Hyper-Ackermannian bounds for pushdown vector addition systems
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• The ordinal-recursive complexity of timed-arc Petri nets, data nets, and other enriched nets
• Well-structured pushdown systems

Cited in

(5)

• Coverability Is undecidable in one-dimensional pushdown vector addition systems with resets
• A lower bound for the coverability problem in acyclic pushdown VAS
• Well-structured pushdown systems
• Solving Coverability Problem for Monotonic Counter Systems by Supercompilation
• Equivalences of Pushdown Systems Are Hard

This page was built for publication: Hardness results for coverability problem of well-structured pushdown systems

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