Amir M. Ben-Amram

76 papers A* 11A 2B 3C 1Journal 51Unranked 7
YearRankTypeTitle / Venue / Authors
2025 J jnl
A degree structure on representations of irrational numbers.
J. Log. Anal.
Amir M. Ben-Amram, Lars Kristiansen
2025 J jnl
On Representations of irrational numbers and the Computational Complexity of Converting between such Representations.
Bull. Symb. Log.
Amir M. Ben-Amram, Lars Kristiansen, Jakob Grue Simonsen
2025 J jnl
Termination Analysis of Linear-Constraint Programs.
CoRR
Amir M. Ben-Amram, Samir Genaim, Joël Ouaknine, James Worrell
2023 J jnl
On representations of real numbers and the computational complexity of converting between such representations.
CoRR
Amir M. Ben-Amram, Lars Kristiansen, Jakob Grue Simonsen
2021 J jnl
Tight Polynomial Bounds for Loop Programs in Polynomial Space.
Log. Methods Comput. Sci.
Amir M. Ben-Amram, Geoff W. Hamilton
2020 J jnl
Tight Polynomial Bounds for Loop Programs in Polynomial Space.
CoRR
Amir M. Ben-Amram, Geoff W. Hamilton
2020 J jnl
Tight Polynomial Worst-Case Bounds for Loop Programs.
Log. Methods Comput. Sci.
Amir M. Ben-Amram, Geoff W. Hamilton
2019 B conf
Multiphase-Linear Ranking Functions and Their Relation to Recurrent Sets.
SAS
Amir M. Ben-Amram, Jesús J. Doménech, Samir Genaim
2019 J jnl
Tight Polynomial Worst-Case Bounds for Loop Programs.
CoRR
Amir M. Ben-Amram, Geoff W. Hamilton
2019 B conf
Tight Worst-Case Bounds for Polynomial Loop Programs.
FoSSaCS
Amir M. Ben-Amram, Geoff W. Hamilton
2018 J jnl
Multiphase-Linear Ranking Functions and their Relation to Recurrent Sets.
CoRR
Amir M. Ben-Amram, Jesús Doménech, Samir Genaim
2017 — conf
On Multiphase-Linear Ranking Functions.
CAV (2)
Amir M. Ben-Amram, Samir Genaim
2017 J jnl
On Multiphase-Linear Ranking Functions.
CoRR
Amir M. Ben-Amram, Samir Genaim
2016 — conf
Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate.
VPT@ETAPS
Amir M. Ben-Amram, Aviad Pineles
2015 — conf
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions.
CAV (2)
Amir M. Ben-Amram, Samir Genaim
2015 J jnl
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions.
CoRR
Amir M. Ben-Amram, Samir Genaim
2015 J jnl
Mortality of iterated piecewise affine functions over the integers: Decidability and complexity.
Comput.
Amir M. Ben-Amram
2014 J jnl
Ranking Functions for Linear-Constraint Loops.
J. ACM
Amir M. Ben-Amram, Samir Genaim
2014 — conf
The Hardness of Finding Linear Ranking Functions for Lasso Programs.
GandALF
Amir M. Ben-Amram
2013 J jnl
A Comment on Budach's Mouse-in-an-Octant Problem
CoRR
Amir M. Ben-Amram
2013 A conf
Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract).
STACS
Amir M. Ben-Amram
2013 A* conf
On the linear ranking problem for integer linear-constraint loops.
POPL
Amir M. Ben-Amram, Samir Genaim
2013 — conf
Ranking Functions for Linear-Constraint Loops.
VPT@CAV
Amir M. Ben-Amram
2012 J jnl
Bounded Termination of Monotonicity-Constraint Transition Systems
CoRR
Amir M. Ben-Amram, Michael Vainer
2012 J jnl
Computational Models with No Linear Speedup.
Chic. J. Theor. Comput. Sci.
Amir M. Ben-Amram, Niels H. Christensen, Jakob Grue Simonsen
2012 J jnl
Corrigendum to "A simple and efficient Union-Find-Delete algorithm" [Theoret. Comput. Sci. 412(4-5) 487-492].
Theor. Comput. Sci.
Amir M. Ben-Amram, Simon Yoffe
2012 J jnl
Monotonicity Constraints in Characterizations of PSPACE.
J. Log. Comput.
Amir M. Ben-Amram, Bruno Loff, Isabel Oitavem
2012 J jnl
On the Edge of Decidability in Complexity Analysis of Loop Programs.
Int. J. Found. Comput. Sci.
Amir M. Ben-Amram, Lars Kristiansen
2012 J jnl
On the Linear Ranking Problem for Integer Linear-Constraint Loops
CoRR
Amir M. Ben-Amram, Samir Genaim
2012 B conf
On the Termination of Integer Loops.
VMCAI
Amir M. Ben-Amram, Samir Genaim, Abu Naser Masud
2012 J jnl
On the Termination of Integer Loops.
ACM Trans. Program. Lang. Syst.
Amir M. Ben-Amram, Samir Genaim, Abu Naser Masud
2011 J jnl
A simple and efficient Union-Find-Delete algorithm.
Theor. Comput. Sci.
Amir M. Ben-Amram, Simon Yoffe
2011 J jnl
Monotonicity Constraints for Termination in the Integer Domain
Log. Methods Comput. Sci.
Amir M. Ben-Amram
2011 J jnl
SAT-Based Termination Analysis Using Monotonicity Constraints over the Integers
CoRR
Michael Codish, Igor Gonopolskiy, Amir M. Ben-Amram, Carsten Fuhs, Jürgen Giesl
2011 J jnl
SAT-based termination analysis using monotonicity constraints over the integers.
Theory Pract. Log. Program.
Michael Codish, Igor Gonopolskiy, Amir M. Ben-Amram, Carsten Fuhs, Jürgen Giesl
2010 — conf
On Decidable Growth-Rate Properties of Imperative Programs
DICE
Amir M. Ben-Amram
2010 J jnl
Size-Change Termination, Monotonicity Constraints and Ranking Functions
Log. Methods Comput. Sci.
Amir M. Ben-Amram
2009 J jnl
A complexity tradeoff in ranking-function termination proofs.
Acta Informatica
Amir M. Ben-Amram
2009 J jnl
Ranking Functions for Size-Change Termination II
Log. Methods Comput. Sci.
Amir M. Ben-Amram, Chin Soon Lee
2009 A* conf
Size-Change Termination, Monotonicity Constraints and Ranking Functions.
CAV
Amir M. Ben-Amram
2009 J jnl
The Euler Path to Static Level-Ancestors
CoRR
Amir M. Ben-Amram
2008 A conf
A SAT-Based Approach to Size Change Termination with Global Ranking Functions.
TACAS
Amir M. Ben-Amram, Michael Codish
2008 C conf
Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time.
CiE
Amir M. Ben-Amram, Neil D. Jones, Lars Kristiansen
2008 J jnl
Size-change termination with difference constraints.
ACM Trans. Program. Lang. Syst.
Amir M. Ben-Amram
2007 J jnl
Program termination analysis in polynomial time.
ACM Trans. Program. Lang. Syst.
Amir M. Ben-Amram, Chin Soon Lee
2006 J jnl
Backing up in singly linked lists.
J. ACM
Amir M. Ben-Amram, Holger Petersen
2005 J jnl
The Church-Turing thesis and its look-alikes.
SIGACT News
Amir M. Ben-Amram
2004 J jnl
A complexity-theoretic proof of a Recursion-Theoretic Theorem.
SIGACT News
Amir M. Ben-Amram
2003 J jnl
Element distinctness on one-tape Turing machines: a complete solution.
Acta Informatica
Amir M. Ben-Amram, Omer Berkman, Holger Petersen
2003 J jnl
Tighter constant-factor time hierarchies.
Inf. Process. Lett.
Amir M. Ben-Amram
2002 — conf
General Size-Change Termination and Lexicographic Descent.
The Essence of Computation
Amir M. Ben-Amram
2002 J jnl
Improved Bounds for Functions Related to Busy Beavers.
Theory Comput. Syst.
Amir M. Ben-Amram, Holger Petersen
2002 J jnl
Lower Bounds for Dynamic Data Structures on Algebraic RAMs.
Algorithmica
Amir M. Ben-Amram, Zvi Galil
2001 J jnl
A Generalization of a Lower Bound Technique due to Fredman and Saks.
Algorithmica
Amir M. Ben-Amram, Zvi Galil
2001 A* conf
The size-change principle for program termination.
POPL
Chin Soon Lee, Neil D. Jones, Amir M. Ben-Amram
2001 J jnl
Topological Lower Bounds on Algebraic Random Access Machines.
SIAM J. Comput.
Amir M. Ben-Amram, Zvi Galil
2000 J jnl
Computational complexity via programming languages: constant factors do matter.
Acta Informatica
Amir M. Ben-Amram, Neil D. Jones
1999 J jnl
A Precise Version of a Time Hierarchy Theorem.
Fundam. Informaticae
Amir M. Ben-Amram, Neil D. Jones
1999 A* conf
Backing Up in Singly Linked Lists.
STOC
Amir M. Ben-Amram, Holger Petersen
1999 A* conf
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).
STOC
Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe
1998 A* conf
CONS-Free Programs with Tree Input (Extended Abstract).
ICALP
Amir M. Ben-Amram, Holger Petersen
1998 J jnl
Introducing: Reasonable Complete Programming Languages.
Bull. EATCS
Amir M. Ben-Amram
1997 J jnl
When Can We Sort in o(n log n) Time?
J. Comput. Syst. Sci.
Amir M. Ben-Amram
1996 J jnl
A Note on Busy Beavers and Other Creatures.
Math. Syst. Theory
Amir M. Ben-Amram, Bryant A. Julstrom, Uri Zwick
1995 A* conf
Lower Bounds on Algebraic Random Access Machines (Extended Abstract).
ICALP
Amir M. Ben-Amram, Zvi Galil
1995 J jnl
On Data Structure Tradeoffs and an Application to Union-Find
Electron. Colloquium Comput. Complex.
Amir M. Ben-Amram, Zvi Galil
1995 J jnl
On the Power of the Shift Instruction
Inf. Comput.
Amir M. Ben-Amram, Zvi Galil
1995 — —
On the power of random access machines
Amir M. Ben-Amram
1995 J jnl
What is a "pointer machine"?
SIGACT News
Amir M. Ben-Amram
1994 A* conf
The Subtree Max Gap Problem with Application to Parallel String Covering.
SODA
Amir M. Ben-Amram, Omer Berkman, Costas S. Iliopoulos, Kunsoo Park
1994 J jnl
Unit-Cost Pointers versus Logarithmic-Cost Addresses.
Theor. Comput. Sci.
Amir M. Ben-Amram
1993 A* conf
When can we sort in o(n log n) time?
FOCS
Amir M. Ben-Amram, Zvi Galil
1992 J jnl
On Pointers versus Addresses.
J. ACM
Amir M. Ben-Amram, Zvi Galil
1991 A* conf
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)
FOCS
Amir M. Ben-Amram, Zvi Galil
1991 J jnl
Some notions on notations.
SIGACT News
Amir M. Ben-Amram
1988 A* conf
On Pointers versus Addresses (Extended Abstract)
FOCS
Amir M. Ben-Amram, Zvi Galil