A Logical Characterisation of Event Recording Automata

A Logical Characterisation of Event Recording Automata

Deepak D'Souza

Proc. FTRTFT 2000, Pune (2000)


Abstract

We show that the class of Event Recording Automata [AFH94] admit a logical characterisation via an unrestricted monadic second order logic interpreted over timed words. We point out the closure properties corresponding to existential quantification in the logic. A timed temporal logic considered earlier in the literature is shown to be expressively complete with respect to our monadic logic.

The results in this paper extend smoothly to the class of Event Clock Automata (also introduced in [AFH94]).


Available as a gzipped dvi file (23 K) or gzipped postscript file (75 K).