Event-Clock Automata: From Theory to Practice

Details Event-Clock Automata: From Theory to Practice Event-Clock Automata: From Theory to Practice

2011-07-20

arxiv.org/abs/1107.4138v2

Computer Science

Logic in Computer Science

Full version of the FORMATS 2011 version

Scientific paper

Event clock automata (ECA) are a model for timed languages that has been introduced by Alur, Fix and Henzinger as an alternative to timed automata, with better theoretical properties (for instance, ECA are determinizable while timed automata are not). In this paper, we revisit and extend the theory of ECA. We first prove that no finite time abstract language equivalence exists for ECA, thereby disproving a claim in the original work on ECA. This means in particular that regions do not form a time abstract bisimulation. Nevertheless, we show that regions can still be used to build a finite automaton recognizing the untimed language of an ECA. Then, we extend the classical notions of zones and DBMs to let them handle event clocks instead of plain clocks (as in timed automata) by introducing event zones and Event DBMs (EDBMs). We discuss algorithms to handle event zones represented as EDBMs, as well as (semi-) algorithms based on EDBMs to decide language emptiness of ECA.

Affiliated with

Also associated with

No associations

Rating

Event-Clock Automata: From Theory to Practice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Event-Clock Automata: From Theory to Practice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Event-Clock Automata: From Theory to Practice will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-687215