Amir M. BenAmram
According to our database^{1},
Amir M. BenAmram
authored at least 63 papers
between 1988 and 2017.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at dl.acm.org
On csauthors.net:
Bibliography
2017
On MultiphaseLinear Ranking Functions.
CoRR, 2017
On MultiphaseLinear Ranking Functions.
Proceedings of the Computer Aided Verification  29th International Conference, 2017
2016
Flowchart Programs, Regular Expressions, and Decidability of Polynomial GrowthRate.
Proceedings of the Fourth International Workshop on Verification and Program Transformation, 2016
2015
Complexity of BradleyMannaSipma Lexicographic Ranking Functions.
CoRR, 2015
Mortality of iterated piecewise affine functions over the integers: Decidability and complexity.
Computability, 2015
Complexity of BradleyMannaSipma Lexicographic Ranking Functions.
Proceedings of the Computer Aided Verification  27th International Conference, 2015
2014
Ranking Functions for LinearConstraint 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 MouseinanOctant 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 linearconstraint loops.
Proceedings of the 40th Annual ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, 2013
Ranking Functions for LinearConstraint 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 UnionFindDelete algorithm" [Theoret. Comput. Sci. 412(45) 487492].
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 LinearConstraint Loops
CoRR, 2012
Bounded Termination of MonotonicityConstraint 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
SATbased termination analysis using monotonicity constraints over the integers.
TPLP, 2011
A simple and efficient UnionFindDelete algorithm.
Theor. Comput. Sci., 2011
SATBased 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 GrowthRate Properties of Imperative Programs
Proceedings of the Proceedings International Workshop on Developments in Implicit Computational complExity, 2010
SizeChange Termination, Monotonicity Constraints and Ranking Functions
Logical Methods in Computer Science, 2010
2009
The Euler Path to Static LevelAncestors
CoRR, 2009
Ranking Functions for SizeChange Termination II
Logical Methods in Computer Science, 2009
A complexity tradeoff in rankingfunction termination proofs.
Acta Inf., 2009
SizeChange Termination, Monotonicity Constraints and Ranking Functions.
Proceedings of the Computer Aided Verification, 21st International Conference, 2009
2008
Sizechange termination with difference constraints.
ACM Trans. Program. Lang. Syst., 2008
A SATBased 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 ChurchTuring thesis and its lookalikes.
SIGACT News, 2005
2004
A complexitytheoretic proof of a RecursionTheoretic Theorem.
SIGACT News, 2004
2003
Tighter constantfactor time hierarchies.
Inf. Process. Lett., 2003
Element distinctness on onetape 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 SizeChange 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 sizechange principle for program termination.
Proceedings of the Conference Record of POPL 2001: The 28th ACM SIGPLANSIGACT 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 ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
WorstCase and Amortised Optimality in UnionFind (Extended Abstract).
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
1998
Introducing: Reasonable Complete Programming Languages.
Bulletin of the EATCS, 1998
CONSFree 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 UnionFind
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
UnitCost Pointers versus LogarithmicCost Addresses.
Theor. Comput. Sci., 1994
The Subtree Max Gap Problem with Application to Parallel String Covering.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 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