Amir M. Ben-Amram

According to our database1, Amir M. Ben-Amram
  • authored at least 63 papers between 1988 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
On Multiphase-Linear Ranking Functions.
CoRR, 2017

On Multiphase-Linear Ranking Functions.
Proceedings of the Computer Aided Verification - 29th International Conference, 2017

2016
Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate.
Proceedings of the Fourth International Workshop on Verification and Program Transformation, 2016

2015
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions.
CoRR, 2015

Mortality of iterated piecewise affine functions over the integers: Decidability and complexity.
Computability, 2015

Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions.
Proceedings of the Computer Aided Verification - 27th International Conference, 2015

2014
Ranking Functions for Linear-Constraint Loops.
J. ACM, 2014

The Hardness of Finding Linear Ranking Functions for Lasso Programs.
Proceedings of the Proceedings Fifth International Symposium on Games, 2014

2013
A Comment on Budach's Mouse-in-an-Octant Problem
CoRR, 2013

Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract).
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

On the linear ranking problem for integer linear-constraint loops.
Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2013

Ranking Functions for Linear-Constraint Loops.
Proceedings of the First International Workshop on Verification and Program Transformation, 2013

2012
On the Termination of Integer Loops.
ACM Trans. Program. Lang. Syst., 2012

Corrigendum to "A simple and efficient Union-Find-Delete algorithm" [Theoret. Comput. Sci. 412(4-5) 487-492].
Theor. Comput. Sci., 2012

Monotonicity Constraints in Characterizations of PSPACE.
J. Log. Comput., 2012

On the Edge of Decidability in Complexity Analysis of Loop Programs.
Int. J. Found. Comput. Sci., 2012

On the Linear Ranking Problem for Integer Linear-Constraint Loops
CoRR, 2012

Bounded Termination of Monotonicity-Constraint Transition Systems
CoRR, 2012

Computational Models with No Linear Speedup.
Chicago J. Theor. Comput. Sci., 2012

On the Termination of Integer Loops.
Proceedings of the Verification, Model Checking, and Abstract Interpretation, 2012

2011
SAT-based termination analysis using monotonicity constraints over the integers.
TPLP, 2011

A simple and efficient Union-Find-Delete algorithm.
Theor. Comput. Sci., 2011

SAT-Based Termination Analysis Using Monotonicity Constraints over the Integers
CoRR, 2011

Monotonicity Constraints for Termination in the Integer Domain
Logical Methods in Computer Science, 2011

2010
On Decidable Growth-Rate Properties of Imperative Programs
Proceedings of the Proceedings International Workshop on Developments in Implicit Computational complExity, 2010

Size-Change Termination, Monotonicity Constraints and Ranking Functions
Logical Methods in Computer Science, 2010

2009
The Euler Path to Static Level-Ancestors
CoRR, 2009

Ranking Functions for Size-Change Termination II
Logical Methods in Computer Science, 2009

A complexity tradeoff in ranking-function termination proofs.
Acta Inf., 2009

Size-Change Termination, Monotonicity Constraints and Ranking Functions.
Proceedings of the Computer Aided Verification, 21st International Conference, 2009

2008
Size-change termination with difference constraints.
ACM Trans. Program. Lang. Syst., 2008

A SAT-Based Approach to Size Change Termination with Global Ranking Functions.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2008

Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time.
Proceedings of the Logic and Theory of Algorithms, 2008

2007
Program termination analysis in polynomial time.
ACM Trans. Program. Lang. Syst., 2007

2006
Backing up in singly linked lists.
J. ACM, 2006

2005
The Church-Turing thesis and its look-alikes.
SIGACT News, 2005

2004
A complexity-theoretic proof of a Recursion-Theoretic Theorem.
SIGACT News, 2004

2003
Tighter constant-factor time hierarchies.
Inf. Process. Lett., 2003

Element distinctness on one-tape Turing machines: a complete solution.
Acta Inf., 2003

2002
Improved Bounds for Functions Related to Busy Beavers.
Theory Comput. Syst., 2002

Lower Bounds for Dynamic Data Structures on Algebraic RAMs.
Algorithmica, 2002

General Size-Change Termination and Lexicographic Descent.
Proceedings of the Essence of Computation, Complexity, Analysis, 2002

2001
Topological Lower Bounds on Algebraic Random Access Machines.
SIAM J. Comput., 2001

A Generalization of a Lower Bound Technique due to Fredman and Saks.
Algorithmica, 2001

The size-change principle for program termination.
Proceedings of the Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2001

2000
Computational complexity via programming languages: constant factors do matter.
Acta Inf., 2000

1999
A Precise Version of a Time Hierarchy Theorem.
Fundam. Inform., 1999

Backing Up in Singly Linked Lists.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998
Introducing: Reasonable Complete Programming Languages.
Bulletin of the EATCS, 1998

CONS-Free Programs with Tree Input (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997
When Can We Sort in o(n log n) Time?
J. Comput. Syst. Sci., 1997

1996
A Note on Busy Beavers and Other Creatures.
Mathematical Systems Theory, 1996

1995
On the Power of the Shift Instruction
Inf. Comput., February, 1995

What is a "pointer machine"?
SIGACT News, 1995

On Data Structure Tradeoffs and an Application to Union-Find
Electronic Colloquium on Computational Complexity (ECCC), 1995

Lower Bounds on Algebraic Random Access Machines (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994
Unit-Cost Pointers versus Logarithmic-Cost Addresses.
Theor. Comput. Sci., 1994

The Subtree Max Gap Problem with Application to Parallel String Covering.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
When can we sort in o(n log n) time?
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
On Pointers versus Addresses.
J. ACM, 1992

1991
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1988
On Pointers versus Addresses (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988


  Loading...