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 metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229068
Contributor : Elena Giachino <>
Submitted on : Monday, November 16, 2015 - 12:58:55 PM
Last modification on : Wednesday, October 10, 2018 - 10:09:56 AM
Long-term archiving on : Friday, April 28, 2017 - 9:31:45 PM

Files

main.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

282

Files downloads

211