Perturbed timed automata

Rajeev Alur, Salvatore La Torre, P. Madhusudan

Research output: Contribution to journalConference article

Abstract

We consider timed automata whose clocks are imperfect. For a given perturbation error 0 < ε < 1, the perturbed language of a timed automaton is obtained by letting its clocks change at a rate within the interval [1 - ε, 1 + ε]. We show that the perturbed language of a timed automaton with a single clock can be captured by a deterministic timed automaton. This leads to a decision procedure for the language inclusion problem for systems modeled as products of 1-clock automata with imperfect clocks. We also prove that determinization and decidability of language inclusion are not possible for multi-clock automata, even with perturbation.

Original languageEnglish (US)
Pages (from-to)70-85
Number of pages16
JournalLecture Notes in Computer Science
Volume3414
StatePublished - Sep 14 2005
Event8th International Workshop on Hybrid Systems: Computation and Control, HSCC 2005 - Zurich, Switzerland
Duration: Mar 9 2005Mar 11 2005

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this