Relating timed and register automata

Details Relating timed and register automata Relating timed and register automata

2010-11-30

arxiv.org/abs/1011.6432v1

EPTCS 41, 2010, pp. 61-75

Computer Science

Formal Languages and Automata Theory

In Proceedings EXPRESS'10, arXiv:1011.6012

Scientific paper

10.4204/EPTCS.41.5

Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes registers that can store data values for later comparison. Although these two models behave in appearance differently, several decision problems have the same (un)decidability and complexity results for both models. As a prominent example, emptiness is decidable for alternating automata with one clock or register, both with non-primitive recursive complexity. This is not by chance. This work confirms that there is indeed a tight relationship between the two models. We show that a run of a timed automaton can be simulated by a register automaton, and conversely that a run of a register automaton can be simulated by a timed automaton. Our results allow to transfer complexity and decidability results back and forth between these two kinds of models. We justify the usefulness of these reductions by obtaining new results on register automata.

Affiliated with

Also associated with

No associations

Rating

Relating timed and register automata 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 Relating timed and register automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relating timed and register automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444498