Skip to Main content Skip to Navigation
Conference papers

ComplexityParser: An Automatic Tool for Certifying Poly-Time Complexity of Java Programs

Emmanuel Hainry 1 Emmanuel Jeandel 1 Romain Péchoux 1 Olivier Zeyen 1 
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : ComplexityParser is a static complexity analyzer for Java programs providing the first implementation of a tier-based typing discipline. The input is a file containing Java classes. If the main method can be typed and, provided the program terminates, then the program is guaranteed to do so in polynomial time and hence also to have heap and stack sizes polynomially bounded. The application uses antlr to generate a parse tree on which it performs an efficient type inference: linear in the input size, provided that the method arity is bounded by some constant.
Complete list of metadata

https://hal.inria.fr/hal-03337755
Contributor : Emmanuel Hainry Connect in order to contact the contributor
Submitted on : Wednesday, September 8, 2021 - 10:53:23 AM
Last modification on : Sunday, June 26, 2022 - 3:13:00 AM
Long-term archiving on: : Friday, December 10, 2021 - 9:53:49 AM

Files

ictac-tool.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Emmanuel Hainry, Emmanuel Jeandel, Romain Péchoux, Olivier Zeyen. ComplexityParser: An Automatic Tool for Certifying Poly-Time Complexity of Java Programs. ICTAC 2021 - 18th International Colloquium on Theoretical Aspects of Computing, Sep 2021, Nur-Sultan/Virtual, Kazakhstan. pp.357-365, ⟨10.1007/978-3-030-85315-0_20⟩. ⟨hal-03337755⟩

Share

Metrics

Record views

42

Files downloads

78