Ben-Amram, Amir M. and Hamilton, Geoff 
ORCID: 0000-0001-5954-6444
(2019)
Tight Worst-Case Bounds for Polynomial Loop Programs.
In: International Conference on Foundations of Software Science and Computation Structures, 8-11 April 2019, Prague, Czech Republic.
ISBN 978-3-030-17126-1
Abstract
In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple programming language|representing non-deterministic imperative programs with bounded loops, and arithmetics limited to addition and multiplication|it is possible to decide precisely whether a program has certain growth-rate properties, in particular whether a computed value, or the program's running time, has a polynomial growth rate. A natural and intriguing problem was to improve the precision of the information obtained. This paper shows how to obtain asymptotically-tight multivariate polynomial bounds for this class of programs. This is a complete solution: whenever a polynomial bound exists it will be found.
Metadata
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Event Type: | Conference |
| Refereed: | Yes |
| Uncontrolled Keywords: | asymptotically-tight, multivariate, disjunctive, worst-case, polynomial bounds |
| Subjects: | Computer Science > Computational complexity |
| DCU Faculties and Centres: | UNSPECIFIED |
| Published in: | Foundations of Software Science and Computation Structures. Lecture Notes in Computer Science 11425. Springer. ISBN 978-3-030-17126-1 |
| Publisher: | Springer |
| Official URL: | https://link.springer.com/book/10.1007/978-3-030-1... |
| Copyright Information: | Creative Commons Attribution 4.0 International License (Open Access) |
| Funders: | School of Computing, DCU |
| ID Code: | 23428 |
| Deposited On: | 18 Dec 2019 11:50 by Geoffrey Hamilton . Last Modified 06 Nov 2020 12:37 |
Documents
Full text available as:
Preview |
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
347kB |
Downloads
Downloads
Downloads per month over past year
Archive Staff Only: edit this record