References

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