The hardness of finding linear ranking functions for lasso programs

MaRDI QIDQ4995357zbMATH OpenFDO

Authors Amir M. Ben-Amram

Publication date 24 June 2021

Full work available at URL https://arxiv.org/abs/1408.5955, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF2014.6

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• On the \textsc{Linear Ranking} problem for integer linear-constraint loops
• Ranking functions for linear-constraint loops
• Complexity of Bradley-Manna-Sipma lexicographic ranking functions
• Computer Aided Verification
• On the linear ranking problem for simple floating-point loops

Cited in

(5)

• On the linear ranking problem for simple floating-point loops
• Complexity of Bradley-Manna-Sipma lexicographic ranking functions
• On the \textsc{Linear Ranking} problem for integer linear-constraint loops
• Tight polynomial bounds for loop programs in polynomial space
• Ranking functions for linear-constraint loops

This page was built for publication: The hardness of finding linear ranking functions for lasso programs

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