16 papers · ranked by Valyu relevance
Nils Lommen, Éléanore Meyer, Jürgen Giesl
Programs Authors: ['Nils Lommen' 'Éléanore Meyer' 'Jürgen Giesl'] Abstract There exist several approaches to infer runtime or resource bounds for integer programs automatically. In this paper, we study the subclass of periodic rational solvable loops (prs-loops), where questions regarding the runtime and the size of…
Jagriti Sikka, Kushal Satya, Yaman Kumar, Shagun Uppal + 2 more
'Rajiv Ratn Shah' 'Roger Zimmermann'] Abstract. Predicting the runtime complexity of a programming code is an arduous task. In fact, even for humans, it requires a subtle analysis and comprehensive knowledge of algorithms to predict time complexity with high fidelity, given any code. As per Turing's Halting problem…
Nils Lommen, Éléanore Meyer, Jürgen Giesl
KoAT is a tool to automatically infer complexity bounds and prove termination of (possibly recursive) integer programs. To this end, KoAT implements an alternating modular inference of upper runtime and size bounds for program parts. In particular, KoAT uses a portfolio of different techniques to analyze subprograms.…
Nils Lommen, E. Meyer, Jürgen Giesl
There exist several results on deciding termination and computing runtime bounds for triangular weakly non-linear loops (twn-loops). We show how to use results on such subclasses of programs where complexity bounds are computable within incomplete approaches for complexity analysis of full integer programs. To this…
Liye Guo, Deivid Vale
Time complexity in rewriting is naturally understood as the number of steps needed to reduce terms to normal forms. Establishing complexity bounds to this measure is a well-known problem in the rewriting community. A vast majority of techniques to find such bounds consist of modifying termination proofs in order to…
Jürgen Giesl, Nils Lommen, Marcel Hark, Fabian Meyer
In [16], we developed an approach for automatic complexity analysis of integer programs, based on an alternating modular inference of upper runtime and size bounds for program parts. In this paper, we show how recent techniques to improve automated termination analysis of integer programs (like the generation of…
Nils Lommen, Fabian Meyer, Jürgen Giesl
There exist several results on deciding termination and computing runtime bounds for triangular weakly non-linear loops (twn-loops). We show how to use results on such subclasses of programs where complexity bounds are computable within incomplete approaches for complexity analysis of full integer programs. To this…
Sarah Winkler, Georg Moser
Logically constrained rewrite systems (LCTRSs) are a versatile and efficient rewriting formalism that can be used to model programs from various programming paradigms, as well as simplification systems in compilers and SMT solvers. In this paper, we investigate techniques to analyse the worst-case runtime complexity of…
Feng Gu, Julie Greensmith, Uwe Aickelin
As one of the emerging algorithms in the field of Artificial Immune Systems (AIS), the Dendritic Cell Algorithm (DCA) has been successfully applied to a number of challenging real-world problems. However, one criticism is the lack of a formal definition, which could result in ambiguity for understanding the algorithm.…
Krishnendu Chatterjee, Hongfei Fu, Aniket Murhekar
We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. Several classical textbook algorithms have quite efficient expected-runtime complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., QUICK-SORT), or…
Martin Avanzini, Georg Moser
> Abstract. This paper is concerned with the complexity analysis of constructor term rewrite systems and its ramification in implicit computational complexity. We introduce a path order with multiset status, the polynomial path order POP∗ , that is applicable in two related, but distinct contexts. On the one hand POP∗…
Arya Chakraborty
— While time complexity and space complexity of an algorithm helps to determine its efficiency when time or space needs to be optimized respectively, they fail to determine the more efficient algorithm when time and space both need to be optimized simultaneously. This resulted in the development of the A1-Score Factor…
Rome, Hayden, Lynch, Jayson + 6 more
Algorithm research focuses primarily on how many operations processors need to do (time complexity). But for many problems, both the runtime and energy used are dominated by memory accesses. In this paper, we present the first broad survey of how algorithmic progress has improved memory usage (space complexity). We…
Étienne Grandjean, Louis Jachiet
| 1 | Introduction | 2 | |…
David Van Horn
I gratefully acknowledge the support of the following people, groups, and institutions, in no particular order: Matthew Goldfield. Jan Midtgaard. Fritz Henglein. Matthew Might. Ugo Dal Lago. Chung-chieh Shan. Kazushige Terui. Christian Skalka. Shriram Krishnamurthi. Michael Sperber. David McAllester. Mitchell Wand.…
Feng Pan, Heng-Liang Zhang, Jie Qi
Computational complexity is a particularly important objective. The idea of Landauer principle was extended through mapping three classic problems (sorting、 ordered searching and max of N unordered numbers) into Maxwell demon thought experiment in this paper. The problems' complexity is defined on the entropy basis and…