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


Christoph Armin Herrmann, Kevin Hammond

School/Research organisations


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
Publication statusPublished - 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

ID: 15496225