Hardness Results for Coverability Problem of Well-Structured Pushdown Systems

DOI10.1007/978-3-319-53733-7_32zbMath1485.68070OpenAlexW2588725210MaRDI QIDQ5739016

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

automatalower boundspushdown systemscoverability

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

Cites Work

• Unnamed Item
• Algorithmic analysis of programs with well quasi-ordered domains.
• Well-Structured Pushdown Systems
• Analysis of recursively parallel programs
• The Ordinal-Recursive Complexity of Timed-arc Petri Nets, Data Nets, and Other Enriched Nets
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• Hyper-Ackermannian bounds for pushdown vector addition systems

This page was built for publication: Hardness Results for Coverability Problem of Well-Structured Pushdown Systems