Safety Problems Are NP-complete for Flat Integer Programs with Octagonal Loops
From MaRDI portal
Publication:2938069
DOI10.1007/978-3-642-54013-4_14zbMath1428.68160OpenAlexW1489033561MaRDI QIDQ2938069
Radu Iosif, Marius Bozga, Filip Konečný
Publication date: 13 January 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-54013-4_14
Integer programming (90C10) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (7)
Reachability problems on reliable and lossy queue automata ⋮ Equivalence Between Model-Checking Flat Counter Systems and Presburger Arithmetic ⋮ Equivalence between model-checking flat counter systems and Presburger arithmetic ⋮ Interprocedural Reachability for Flat Integer Programs ⋮ Verification of Flat FIFO Systems ⋮ Unnamed Item ⋮ Taming past LTL and flat counter systems
Uses Software
This page was built for publication: Safety Problems Are NP-complete for Flat Integer Programs with Octagonal Loops
