Inductive Composition of Numbers with Maximum, Minimum, and Addition - A New Theory for Program Execution-Time Analysis
Resource
International Journal of Foundations of Computer Science 15 (6): 865-892
Journal
International Journal of Foundations of Computer Science
Journal Volume
15
Journal Issue
6
Pages
865-892
Date Issued
2004-12
Author(s)
Abstract
We extend the classic work of R.J. Parikh on context-free languages with operators min and max on unary alphabet. The new theory is called CAN (Compositional Algebra of Numbers) and can be used to model software processes that can be concatenated, concurrently executed, and recursively invoked. We propose and analyze an algorithm which constructs the execution time sets of a CAN in semilinear form. Finally, we consider several interesting variations of CAN whose execution time sets can be constructed with algorithms.
SDGs
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
06.pdf
Size
2.93 MB
Format
Adobe PDF
Checksum
(MD5):df65f4e84b1c0983ed9a2c5800db154c