69 citations · 153 across the 16 of their papers we have counts for
8 papers · 1 filter
Tight Polynomial Bounds for Loop Programs in Polynomial Space
A. M. Ben-Amram, G. W. Hamilton
We consider the following problem: given a program, find tight asymptotic bounds on the values of some variables at the end of the computation (or at any given program point) in te…
Tight Polynomial Worst-Case Bounds for Loop Programs
Amir M. Ben-Amram, Geoff Hamilton
In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple programming language - representing non-deterministic imperative programs with bounded loops, and arithmetics lim…
The Hardness of Finding Linear Ranking Functions for Lasso Programs
Amir M. Ben-Amram
Finding whether a linear-constraint loop has a linear ranking function is an important key to understanding the loop behavior, proving its termination and establishing iteration bo…
Bounded Termination of Monotonicity-Constraint Transition Systems
Amir M. Ben-Amram, Michael Vainer
Intuitively, if we can prove that a program terminates, we expect some conclusion regarding its complexity. But the passage from termination proofs to complexity bounds is not alwa…
Monotonicity Constraints for Termination in the Integer Domain
Amir M. Ben-Amram
Size-Change Termination (SCT) is a method of proving program termination based on the impossibility of infinite descent. To this end we use a program abstraction in which transitio…
On Decidable Growth-Rate Properties of Imperative Programs
Amir M. Ben-Amram
In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple "core" programming language - an imperative language with bounded loops, and arithmetics limited to addition and…