Bridging Semantics and Complexity: a new approach Prof. M. P. Schellekens National University of Ireland, Cork (UCC) Abstract: Denotational semantics, due to its compositional nature, facilitates program specification. Bridging Semantics and Complexity has been a long standing problem, with as underlying motivation the use of compositionality to facilitate complexity analysis. The solution of this problem has potential implications for Real-Time Language design/static timing. We discuss compositionality for the particular case of the average-case complexity measure, with a focus on the novel language MOQA (MOdular Quantitative Analysis). MOQA enables the modular (compositional) derivation of average-case time complexity of MOQA-programs. The language and its applications form the focus of a book (to appear with Springer). We will show how compositionality can be realized at a complexity level through the notion of random bag preservation and discuss the static timing tool Distri-Track which enables the automated derivation of the average-time of MOQA programs (implemented in Java). Finally, we will discuss some potential avenues to investigate models for this language.