Hyper-Ackermannian bounds for pushdown vector addition systems

DOI10.1145/2603088.2603146zbMATH Open1392.68307OpenAlexW2082102587MaRDI QIDQ4635648FDOQ4635648

Grégoire Sutre, Jérôme Leroux, M. Praveen

Publication date: 23 April 2018

Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2603088.2603146

zbMATH Keywords

nested wordsvector addition systemsboundedness problemhyper-Ackermannian complexitywell-structured pushdown systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (9)

• Hardness Results for Coverability Problem of Well-Structured Pushdown Systems
• Title not available (Why is that?)
• A lower bound for the coverability problem in acyclic pushdown VAS
• On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems
• Nested Timed Automata with Frozen Clocks
• Decidable models of integer-manipulating programs with recursive parallelism
• On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
• Data flow analysis of asynchronous systems using infinite abstract domains
• Title not available (Why is that?)

   Recommendations

• On boundedness problems for pushdown vector addition systems 👍 👎
• On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems 👍 👎
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states 👍 👎
• The Complexity of Reachability in Affine Vector Addition Systems with States 👍 👎
• Title not available (Why is that?) 👍 👎
• The polynomial complexity of vector addition systems with states 👍 👎
• On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• A multiparameter analysis of the boundedness problem for vector addition systems 👍 👎

This page was built for publication: Hyper-Ackermannian bounds for pushdown vector addition systems

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