Title: From Shapes to Amortized Complexity
Language: English
Authors: Fiedor, Tomáš 
Holík, Lukáš 
Rogalewicz, Adam 
Sinn, Moritz
Vojnar, Tomáš 
Zuleger, Florian
Issue Date: 2018
Abstract: 
We propose a new method for the automated resource bound analysis of programs manipulating dynamic data structures built on top of an underlying shape and resource bound analysis. Our approach first constructs an integer abstraction for the input program using information gathered by a shape analyser; then a resource bound analyzer is run on the resulting integer program. The integer abstraction is based on shape norms — numerical measures on dynamic data structures (e.g., the length of a linked list). In comparison to related approaches, we consider a larger class of shape norms which we derive by a lightweight program analysis. The analysis identifies paths through the involved dynamic data structures, and filters the norms which are unlikely to be useful for the later bound analysis. We present a calculus for deriving the numeric changes of the shape norms, thereby generating the integer program. Our calculus encapsulates the minimal information which is required from the shape analysis.

We have implemented our approach on top of the Forester shape analyser and evaluated it on a number of programs manipulating various list and tree structures using the Loopus tool as the underlying bounds analyser. We report on programs with complex data structures and/or using complex algorithms that could not be analysed in a fully automated and precise way before.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:3-3626
http://hdl.handle.net/20.500.12708/912
Library ID: AC15093557
ISBN: 9783319737201
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Inproceedings
Konferenzbeitrag
Appears in Collections:Conference Paper

Files in this item:

File Description SizeFormat
Fiedor Tomas - 2018 - From Shapes to Amortized Complexity.pdf426.05 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

49
checked on Apr 11, 2021

Download(s)

206
checked on Apr 11, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.