Login (DCU Staff Only)
Login (DCU Staff Only)

DORAS | DCU Research Repository

Explore open access research and scholarly works from DCU

Advanced Search

Tight polynomial worst-case bounds for loop programs

Ben-Amram, Amir M. and Hamilton, Geoff orcid logoORCID: 0000-0001-5954-6444 (2020) Tight polynomial worst-case bounds for loop programs. Logical Methods in Computer Science, 16 (2). ISSN 1860-5974

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 move from answering the decision problem to giving a quantitative result, namely, a tight polynomial upper bound. This paper shows how to obtain asymptotically-tight, multivariate, disjunctive polynomial bounds for this class of programs. This is a complete solution: whenever a polynomial bound exists it will be found. A pleasant surprise is that the algorithm is quite simple; but it relies on some subtle reasoning. An important ingredient in the proof is the forest factorization theorem, a strong structural result on homomorphisms into a finite monoid.
Item Type:Article (Published)
Subjects:Computer Science > Computational complexity
DCU Faculties and Centres:DCU Faculties and Schools > Faculty of Engineering and Computing > School of Computing
Official URL:https://doi.org/10.23638/LMCS-16(2:4)2020
Copyright Information:© 2020 The Authors. Open Access (CC-BY 4.0)
ID Code:27089
Deposited On:06 May 2022 13:24 by Geoffrey Hamilton . Last Modified 06 May 2022 13:24

Full text available as:

[thumbnail of LMCS20.pdf]
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Downloads per month over past year

Archive Staff Only: edit this record