@article(Albert-et-al:TCS:2011, author = {Elvira Albert and Puri Arenas and Samir Genaim and German Puebla and Damiano Zanardini}, year = {2012}, title = {Cost analysis of object-oriented bytecode programs}, journal = {Theoretical Computer Science}, volume = {413}, number = {1}, pages = {142--159}, doi = {10.1016/j.tcs.2011.07.009}, ) @inproceedings(ADFG:2010, author = {Christophe Alias and Alain Darte and Paul Feautrier and Laure Gonnord}, year = {2010}, title = {Multi-dimensional Rankings, Program Termination, and Complexity Bounds of Flowchart Programs}, booktitle = {Static Analysis, Proceedings of the 17th International Symposium}, series = {LNCS}, volume = {6337}, publisher = {Springer}, pages = {117--133}, doi = {10.1007/978-3-642-15769-1\_8}, ) @article(BC:92, author = {Stephen Bellantoni and Stephen A. Cook}, year = {1992}, title = {A New Recursion-Theoretic Characterization of the Polytime Functions}, journal = {Computational Complexity}, volume = {2}, pages = {97--110}, doi = {10.1007/BF01201998}, ) @inproceedings(B2010:DICE, author = {Ben-Amram, Amir M.}, year = {2010}, title = {On Decidable Growth-Rate Properties of Imperative Programs}, editor = {Patrick Baillot}, booktitle = {International Workshop on Developments in Implicit Computational complExity (DICE 2010)}, series = {EPTCS}, volume = {23}, pages = {1--14}, doi = {10.4204/EPTCS.23.1}, ) @article(BA:mcInts, author = {Ben-Amram, Amir M.}, year = {2011}, title = {Monotonicity Constraints for Termination in the Integer Domain}, journal = {Logical Methods in Computer Science}, volume = {7}, pages = {1--43}, doi = {10.2168/LMCS-7(3:4)2011}, ) @inproceedings(BJK08, author = {{Ben-Amram}, Amir M. and Neil D. Jones and Lars Kristiansen}, year = {2008}, title = {Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time}, booktitle = {Logic and Theory of Algorithms, Fourth Conference on Computability in Europe, {CiE} 2008}, series = {LNCS}, volume = {5028}, publisher = {Springer}, pages = {67--76}, doi = {10.1007/978-3-540-69407-6\_7}, ) @article(BK11, author = {Ben-Amram, Amir M. and Lars Kristiansen}, year = {2012}, title = {On the Edge of Decidability in Complexity Analysis of Loop Programs}, journal = {International Journal on the Foundations of Computer Science}, volume = {23}, number = {7}, pages = {1451--1464}, doi = {10.1142/S0129054112400588}, ) @article(BP:flowcharts-TR, author = {Ben-Amram, Amir M. and Aviad Pineles}, year = {2016}, title = {Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate}, journal = {CoRR Technical Report}, volume = {1410.4011v4}, url = {http://arxiv.org/abs/1410.4011v4}, ) @article(Benzinger01, author = {Ralph Benzinger}, year = {2001}, title = {Automated complexity analysis of Nuprl extracted programs}, journal = {Journal of Functional Programming}, volume = {11}, number = {1}, pages = {3--31}, doi = {10.1017/S0956796800003865}, ) @article(BCMT:01, author = {Guillaume Bonfante and Adam Cichon and Jean-Yves Marion and H{\'e}l{\`e}ne Touzet}, year = {2001}, title = {Algorithms with polynomial interpretation termination proof}, journal = {Journal of Functional Programming}, volume = {11}, pages = {33--53}, doi = {10.1017/S0956796800003877}, ) @inproceedings(Giesl:TACAS2014, author = {Marc Brockschmidt and Fabian Emmes and Stephan Falke and Carsten Fuhs and J{\"u}rgen Giesl}, year = {2014}, title = {Alternating Runtime and Size Complexity Analysis of Integer Programs}, booktitle = {20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)}, pages = {140--155}, doi = {10.1007/978-3-642-54862-8\_10}, ) @inproceedings(Chin:1992:fusion, author = {Wei-Ngan Chin}, year = {1992}, title = {Safe Fusion of Functional Expressions}, booktitle = {Proceedings of the 1992 ACM Conference on {LISP} and Functional Programming}, series = {LFP '92}, publisher = {ACM}, pages = {11--20}, doi = {10.1145/141471.141494}, ) @inproceedings(Cousot05, author = {Patrick Cousot}, year = {2005}, title = {Proving program invariance and termination by parametric abstraction, Lagrangian relaxation, and semidefinite programming}, booktitle = {6th International Conference on Verification, Model Checking and Abstract Interpretation ({VMCAI}’05)}, series = {LNCS}, volume = {3385}, publisher = {Springer}, pages = {1--–24}, doi = {10.1007/978-3-540-30579-8\_1}, ) @article(DebrayLin93, author = {Saumya Debray and Nai wei Lin}, year = {1993}, title = {Cost Analysis of Logic Programs}, journal = {ACM Transactions on Programming Languages and Systems}, volume = {15}, pages = {48--62}, doi = {10.1145/161468.161472}, ) @article(Eggan1963, author = {Lawrence C. Eggan}, year = {1963}, title = {Transition graphs and the star-height of regular events.}, journal = {The Michigan mathematical journal}, volume = {10}, number = {4}, pages = {385--397}, doi = {10.1307/mmj/1028998975}, ) @article(Goerdt1992, author = {Andreas Goerdt}, year = {1992}, title = {Characterizing complexity classes by general recursive definitions in higher types}, journal = {Information and Computation}, volume = {101}, number = {2}, pages = {202 -- 218}, doi = {10.1016/0890-5401(92)90062-K}, ) @inproceedings(SPEED-POPL09, author = {Sumit Gulwani and Krishna K. Mehra and Trishul M. Chilimbi}, year = {2009}, title = {{SPEED}: precise and efficient static estimation of program computational complexity}, editor = {Zhong Shao and Benjamin C. Pierce}, booktitle = {Proceedings of the 36th {ACM} {SIGPLAN}-{SIGACT} Symposium on Principles of Programming Languages, {POPL} 2009}, publisher = {ACM}, pages = {127--139}, doi = {10.1145/1480881.1480898}, ) @article(Hofmann:iandc2003, author = {Martin Hofmann}, year = {2003}, title = {Linear types and non-size-increasing polynomial time computation}, journal = {Information and Computation}, volume = {183}, number = {1}, pages = {57--85}, doi = {10.1016/S0890-5401(03)00009-9}, ) @article(JK08, author = {Neil D. Jones and Lars Kristiansen}, year = {2009}, title = {A Flow Calculus of mwp-Bounds for Complexity Analysis}, journal = {ACM Trans. Computational Logic}, volume = {10}, number = {4}, pages = {1--41}, doi = {10.1145/1555746.1555752}, ) @inproceedings(Jost:2010, author = {Steffen Jost and Kevin Hammond and Hans-Wolfgang Loidl and Martin Hofmann}, year = {2010}, title = {Static determination of quantitative resource usage for higher-order programs}, booktitle = {The 37th annual ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages}, series = {(POPL)}, publisher = {ACM}, pages = {223--236}, doi = {10.1145/1706299.1706327}, ) @article(KasaiAdachi:80, author = {Takumi Kasai and Akeo Adachi}, year = {1980}, title = {A Characterization of Time Complexity by Simple Loop Programs}, journal = {Journal of Computer and System Sciences}, volume = {20}, number = {1}, pages = {1--17}, doi = {10.1016/0022-0000(80)90001-X}, ) @article(KN04, author = {Lars Kristiansen and Karl-Heinz Niggl}, year = {2004}, title = {On the computational complexity of imperative programming languages}, journal = {Theoretical Computer Science}, volume = {318}, number = {1-2}, pages = {139--161}, doi = {10.1016/j.tcs.2003.10.016}, ) @article(ACE, author = {Le M\'{e}tayer, Daniel}, year = {1988}, title = {{ACE}: an automatic complexity evaluator}, journal = {ACM Trans. Program. Lang. Syst.}, volume = {10}, number = {2}, pages = {248--266}, doi = {10.1145/42190.42347}, ) @inproceedings(leejonesbenamram01, author = {Chin Soon Lee and Neil D. Jones and Ben-Amram, Amir M.}, year = {2001}, title = {The Size-Change Principle for Program Termination}, booktitle = {Proceedings of the Twenty-Eigth {ACM} Symposium on Principles of Programming Languages (POPL), January 2001}, publisher = {ACM press}, pages = {81--92}, doi = {10.1145/360204.360210}, ) @inproceedings(MR:67, author = {Albert R. Meyer and Dennis M. Ritchie}, year = {1967}, title = {The complexity of loop programs}, booktitle = {Proc. 22nd ACM National Conference}, address = {Washington, DC}, pages = {465--469}, ) @incollection(SAFE-FOPARA2010, author = {Manuel Montenegro and Pe\~na, Ricardo and Clara Segura}, year = {2010}, title = {A Space Consumption Analysis by Abstract Interpretation}, booktitle = {Foundational and Practical Aspects of Resource Analysis}, series = {LNCS}, volume = {6324}, publisher = {Springer}, pages = {34--50}, doi = {10.1007/978-3-642-15331-0\_3}, ) @article(NW06, author = {Karl-Heinz Niggl and Henning Wunderlich}, year = {2006}, title = {Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs}, journal = {SIAM J. Comput}, volume = {35}, number = {5}, pages = {1122--1147}, doi = {10.1137/S0097539704445597}, ) @unpublished(Pineles:2014, author = {Aviad Pineles}, year = {2014}, title = {Growth-Rate Analysis of Flowchart Programs}, url = {http://www2.mta.ac.il/~amirben/projects/aviad_final.pdf}, note = {MSc project, The Academic College of Tel-Aviv Yaffo}, ) @article(rival2007trace, author = {Xavier Rival and Laurent Mauborgne}, year = {2007}, title = {The trace Partitioning Abstract Domain}, journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)}, volume = {29}, number = {5}, pages = {26}, doi = {10.1145/1275497.1275501}, ) @inproceedings(Rosendahl89, author = {M. Rosendahl}, year = {1989}, title = {Automatic Complexity Analysis}, booktitle = {Proceedings of the Conference on Functional Programming Languages and Computer Architecture {FPCA}'89}, publisher = {ACM}, pages = {144--156}, doi = {10.1145/99370.99381}, ) @article(Hermengildo-atal.ICLP14, author = {Alejandro Serrano and L{\'{o}}pez{-}Garc{\'{\i}}a, Pedro and Manuel V. Hermenegildo}, year = {2014}, title = {Resource Usage Analysis of Logic Programs via Abstract Interpretation Using Sized Types}, journal = {{TPLP}}, volume = {14}, number = {4-5}, pages = {739--754}, doi = {10.1017/S147106841400057X}, ) @book(Sipser:TOC:3rd, author = {Michael Sipser}, year = {2012}, title = {Introduction to the theory of computation}, edition = {3rd}, publisher = {PWS Publishing Company}, ) @article(Wegbreit:75, author = {Ben Wegbreit}, year = {1975}, title = {Mechanical Program Analysis}, journal = {Communications of the ACM}, volume = {18}, number = {9}, pages = {528--539}, doi = {10.1145/361002.361016}, ) @inproceedings(ZGSV-sas11, author = {Florian Zuleger and Sumit Gulwani and Moritz Sinn and Helmut Veith}, year = {2011}, title = {Bound Analysis of Imperative Programs with the Size-Change Abstraction}, booktitle = {Proceedings of the 8th International Symposium on Static Analysis, SAS 2011}, series = {LNCS}, volume = {6887}, pages = {280--297}, doi = {10.1007/978-3-642-23702-7\_22}, )