Nonelementary Complexities for Branching VASS, MELL, and Extensions

DOI10.1145/2733375zbMath1354.68128arXiv1401.6785OpenAlexW2568513581MaRDI QIDQ2946760

Sylvain Schmitz, Ranko Lazić

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic, 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://arxiv.org/abs/1401.6785

zbMATH Keywords

linear logicsubstructural logicvector addition systemsfast-growing complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Related Items

On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension ⋮ Interprocedural Reachability for Flat Integer Programs ⋮ Coverability and Termination in Recursive Petri Nets ⋮ Logics of Repeating Values on Data Trees and Branching Counter Systems ⋮ ML and Extended Branching VASS ⋮ On the decision problem for MELL ⋮ The ideal view on Rackoff's coverability technique ⋮ The Parametric Complexity of Lossy Counter Machines ⋮ Complexity Hierarchies beyond Elementary ⋮ Coverability, Termination, and Finiteness in Recursive Petri Nets

Cites Work

• Unnamed Item
• Unnamed Item
• The reachability problem for branching vector addition systems requires doubly-exponential space
• Decision problems for propositional linear logic
• The covering and boundedness problems for vector addition systems
• Decidability of linear affine logic
• Petri nets, Horn programs, linear logic and vector games
• The covering and boundedness problems for branching vector addition systems
• Rewriting and typed lambda calculi. Joint international conference, RTA-TLCA 2014, held as part of the Vienna summer of logic, VSL 2014, Vienna, Austria, July 14--17, 2014. Proceedings
• Complexity Hierarchies beyond Elementary
• Solving Parity Games on Integer Vectors
• Alternating Vector Addition Systems with States
• Analysis of recursively parallel programs
• Nondeterministic Phase Semantics and the Undecidability of Boolean BI
• Two-variable logic on data trees and XML reasoning
• Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets
• The Complexity of the Finite Containment Problem for Petri Nets
• Alternation
• The finite model property for various fragments of intuitionistic linear logic
• The finite model property for various fragments of linear logic
• The complexity of decision procedures in relevance logic II
• Hierarchies of number-theoretic functions. I
• Intuitionistic Light Affine Logic