Hyper-Ackermannian bounds for pushdown vector addition systems

DOI10.1145/2603088.2603146MaRDI QIDQ4635648zbMATH OpenOpenAlexFDO

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

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

boundedness problemhyper-Ackermannian complexitynested wordsvector addition systemswell-structured pushdown systems

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 7407775
• The polynomial complexity of vector addition systems with states
• On the coverability problem for pushdown vector addition systems in one dimension
• scientific article; zbMATH DE number 4092784
• scientific article; zbMATH DE number 3878366
• A multiparameter analysis of the boundedness problem for vector addition systems

Cited in

(13)

• On boundedness problems for pushdown vector addition systems
• Data flow analysis of asynchronous systems using infinite abstract domains
• A lower bound for the coverability problem in acyclic pushdown VAS
• Nested timed automata with frozen clocks
• On the coverability problem for pushdown vector addition systems in one dimension
• Reachability for two-counter machines with one test and one reset
• On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems
• On functions weakly computable by pushdown Petri nets and related systems
• Hardness results for coverability problem of well-structured pushdown systems
• Decidable models of integer-manipulating programs with recursive parallelism
• On continuous pushdown VASS in one dimension
• Flattability of priority vector addition systems
• New lower bounds for reachability in 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)