Technical Report 2000-025

A Complete Axiomatisation for Timed Automata

Huimin Lin and Wang Yi

September 2000

Timed automata has been recognised as a fundamental model for real time systems, but it still lacks a satisfactory algebraic theory. This paper fills the gape by presenting a complete proof system for timed automata, in which the equalities between pairs of timed automata that are timed bisimilar can be derived. The proof of the completeness result relies on the introduction of the notion of symbolic timed bisimulation.

Note: A short version of this paper will be included in the proceedings of 20th FST-TCS, 2000

Available as Postscript (319 kB, no cover), PDF (315 kB, no cover), and compressed Postscript (121 kB, no cover)

Download BibTeX entry.