69 citations · 153 across the 16 of their papers we have counts for
6 papers · 1 filter
Termination Analysis of Linear-Constraint Programs
Amir M. Ben-Amram, Samir Genaim, Joël Ouaknine +1
This paper provides an overview of techniques in termination analysis for programs with numerical variables and transitions defined by linear constraints. This subarea of program a…
Multiphase-Linear Ranking Functions and their Relation to Recurrent Sets
Amir M. Ben-Amram, Jesús J. Doménech, Samir Genaim
Multiphase ranking functions (MRFs) are tuples of linear functions that are often used to prove termination of loops in which the computation pr…
On Multiphase-Linear Ranking Functions
Amir M. Ben-Amram, Samir Genaim
Multiphase ranking functions () were proposed as a means to prove the termination of a loop in which the computation progresses through a number of "phases", and th…
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions
Amir M. Ben-Amram, Samir Genaim
In this paper we turn the spotlight on a class of lexicographic ranking functions introduced by Bradley, Manna and Sipma in a seminal CAV 2005 paper, and establish for the first ti…
Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate
Amir M. Ben-Amram, Aviad Pineles
We present a new method for inferring complexity properties for a class of programs in the form of flowcharts annotated with loop information. Specifically, our method can (soundly…
Ranking Functions for Linear-Constraint Loops
Amir M. Ben-Amram, Samir Genaim
In this paper we study the complexity of the problems: given a loop, described by linear constraints over a finite set of variables, is there a linear or lexicographical-linear ran…