An Introduction to Time-Constrained Automata
Abstract
We present timing-constrained automata (TCA), a model for real-time computation in which agents behaviors are modeled by automata constrained by time intervals. In this model time does not change automata behavior: on the contrary, it is automata execution that changes the timing constraints. This allows the model to well lend itself to analysis as well as concrete execution. TCA actions model can have multiple start time and deadlines, can be aperiodic, and can change dynamically following a graph, the time-constrained automaton. This allows expressing much more precise timing constraints than classical periodic or sporadic model, while preserving the ease of scheduling and analysis. We provide some properties of this model as well as their scheduling semantics. We show that timing-constrained tasks can be automatically derived from source-code, and optimally scheduled on single processors using a variant of EDF. We explain how timing constraints can be used to guarantee communication determinism by construction, and used to study when possible agent interactions happens.