Skip to Main content Skip to Navigation
New interface
Conference papers

Time complexity of concurrent programs: a technique based on behavioural types

Elena Giachino 1, 2 Einar Broch Johnsen 3 Cosimo Laneve 1, 2 Ka I Pun 3 
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : We study the problem of automatically computing the time complexity of concurrent object-oriented programs. To determine this complexity we use intermediate abstract descriptions that record relevant information for the time analysis (cost of statements, creations of objects, and concurrent operations), called behavioural types. Then, we define a translation function that takes behavioural types and makes the parallelism explicit into so-called cost equations , which are fed to an automatic off-the-shelf solver for obtaining the time complexity.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Elena Giachino Connect in order to contact the contributor
Submitted on : Monday, November 16, 2015 - 12:58:55 PM
Last modification on : Saturday, June 25, 2022 - 7:47:12 PM
Long-term archiving on: : Friday, April 28, 2017 - 9:31:45 PM


Files produced by the author(s)


  • HAL Id : hal-01229068, version 1
  • ARXIV : 1511.05104



Elena Giachino, Einar Broch Johnsen, Cosimo Laneve, Ka I Pun. Time complexity of concurrent programs: a technique based on behavioural types. FACS 2015, Oct 2015, Niterói, Rio de Janeiro, Brazil. ⟨hal-01229068⟩



Record views


Files downloads