Skip to content

Research at St Andrews

Counter Automata for Parameterised Timing Analysis of Box-Based Systems

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a new compositional approach for analysing the resource usage of reactive box-based systems, as exemplified by Hume. Our analysis deals with a key aspect of reactivity, namely determining the worst-case execution time between some external input event and the associated output event, taking into account repeated box iterations and the possible interactions between boxes in terms of input/output values. In order to achieve this, we capture the system behaviour by abstract interpretation, obtaining counter automata, finite state automata with additional counters that can be used to represent sizes/resource costs and control repetitions. These counter automata precisely capture cost information from the original box-based system, but in a way that is more abstract and therefore easier to analyse. The key contribution of this paper over previous work is that we are able to analyse box-based computations for cyclic systems whose costs may depend on some input parameters and in which the cost formulae are non-linear.


Original languageEnglish
Title of host publicationFoundational and Practical Aspects of Resource Analysis
Subtitle of host publication2nd International Workshop, FOPARA 2011, Madrid, Spain May 19 2011, Revised Selected Papers
EditorsR. Pena, M. van Eekelen, O. Shkaravska
ISBN (Electronic)978-3-642-32495-6
ISBN (Print)978-3-642-32494-9
StatePublished - 2012

Publication series

NameLecture Notes in Computer Science

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatically deriving cost models for structured parallel processes using hylomorphisms

    Castro, D., Hammond, K., Sarkar, S. & Alguwaifli, Y. Feb 2018 In : Future Generation Computer Systems. 79, Part 2, p. 653-668

    Research output: Contribution to journalArticle

  2. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V. Feb 2018 In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

  3. Proof-relevant Horn clauses for dependent type inference and term synthesis

    Farka, F., Komendantskya, E. & Hammond, K. 2018 In : Theory and Practice of Logic Programming. 18, 3-4, p. 484-501

    Research output: Contribution to journalArticle

  4. Type-based cost analysis for lazy functional languages

    Jost, S., Vasconcelos, P., Florido, M. & Hammond, K. Jun 2017 In : Journal of Automated Reasoning. 59, 1, p. 87-120 34 p.

    Research output: Contribution to journalArticle

ID: 15496225