Lower Runtime Bounds for Integer Programs

DOI10.1007/978-3-319-40229-1_37zbMath1475.68134arXiv1911.01077OpenAlexW2471272254MaRDI QIDQ2817952

Matthias Naaf, Florian Frohn, Marc Brockschmidt, Jürgen Giesl, Jera Hensel

Publication date: 5 September 2016

Published in: Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.01077

Mathematics Subject Classification ID

Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Analyzing program termination and complexity automatically with \textsf{AProVE} ⋮ A Calculus for Modular Loop Acceleration ⋮ Lower-bound synthesis using loop specialization and Max-SMT ⋮ From Jinja bytecode to term rewriting: a complexity reflecting transformation ⋮ Lower bounds for runtime complexity of term rewriting ⋮ Lower Runtime Bounds for Integer Programs ⋮ Proving non-termination and lower runtime bounds with \textsf{LoAT} (system description) ⋮ Automatic complexity analysis of integer programs via triangular weakly non-linear loops

Uses Software

• Apron
• z3
• Aspic
• PURRS
• GitHub
• LoAT

Cites Work

• Under-approximating loops in C programs for fast counterexample detection
• Resource Analysis of Complex Programs with Cost Equations
• Lower Runtime Bounds for Integer Programs
• On the Inference of Resource Usage Upper and Lower Bounds
• Combining Widening and Acceleration in Linear Relation Analysis
• Multi-dimensional Rankings, Program Termination, and Complexity Bounds of Flowchart Programs
• Inferring Lower Bounds for Runtime Complexity
• Abstract acceleration of general linear loops
• Multivariate amortized resource analysis
• Computer Aided Verification
• Verification, Model Checking, and Abstract Interpretation

This page was built for publication: Lower Runtime Bounds for Integer Programs