Decomposition of Timed Automata

Kahn Mason (Engineering-Economic Systems and Operations Research, Stanford University, USA)

Padmanabhan Krishnan (Department of Computer Science, University of Canterbury, New Zealand)

Abstract: In this paper we extend the notion of homomorphisms and decomposition to timed automata. This is based on the classical Hartmanis-Stearns decomposition results for finite state automata. As in the classical theory, the existence of non-trivial orthogonal partitions is both necessary and sufficient for non-trivial decompositions. Of course, now these partitions have to include both the set of states and the set of timers (or clocks) in the system. We present an example which illustrate the various issues.

Keywords: parallel decomposition, state and clock partition, timed automata

Categories: F.1.1, J.7