Beschreibung
This book introduces the first programming language for which average-case time analysis of its programs is guaranteed to be modular. The main time measure currently used for real-time languages (worst-case time) is well-known not to be modular in general, which makes average-case analysis notoriously difficult. Schellekens includes sample programs as well as derivations of the average-case time of these programs to illustrate this radically different approach.
Inhaltsverzeichnis
InhaltsangabeIntroductory Notions.- Compositionality.- Random Bag Preservation and Isolated Subsets.- Basic MOQA Operations.- Average-Case Time of Basic MOQA Operations.- The MOQA Language.- Examples of MOQA Programs.- Average-Case Analysis of MOQA programs.- Distri-Track Joint with D. Hickey and M. Boubekeur.- Conclusion and FutureWork.
Autorenporträt
InhaltsangabeForewords by Dana Scott and Greg Bollella.- Preface.- Bridging Semantics and Complexity.- The MOQA Programming Language.- Implications for Real-Time Languages and Automated Average-Case Analysis.- Basic sorting Algorithms.- Compositionality as a Key to Software Timing.- Random Structures.- Series-Parallel MOQA Data Structures.- Examples of MOQA Programs.- Compositional Determination of Average Time.- Examples of Average-Case Analysis in MOQA.- Index.