Timed Automata with non-Instantaneous Actions

Issue title: Concurrency Specification and Programming (CS&P'2000)

Article type: Research Article

Authors: Barbuti, Roberto | De Francesco, Nicoletta | Tesei, Luca

Affiliations: Dipartimento di Informatica, Università di Pisa, Corso Italia, 40 - 56125 Pisa - Italy | Dipartimento di Ingegneria dell'Informazione, Università di Pisa, Via Diotisalvi, 2 - 56126 Pisa - Italy

Abstract: In this paper we propose a model, timed automata with non-instantaneous actions, which allows representing in a suitable way real-time systems. Timed automata with non-instantaneous actions extend the timed automata model by dropping the assumption that actions are instantaneous: in our model an action can take some time to be completed. We investigate the expressiveness of the new model, comparing it with classical timed automata. In particular, we study the set of timed languages which can be accepted by timed automata with non-instantaneous actions. We prove that timed automata with non-instantaneous actions are more expressive than timed automata and less expressive than timed automata with ϵ edges. Moreover we define the parallel composition of timed automata with non-instantaneous actions. We point out how the specification by means of a parallel timed automaton with non-instantaneous actions is, in some cases, more convenient to represent reality.

Keywords: real-time systems, timed automata, timed languages

Journal: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 189-200, 2001