Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Updatable Timed Automata with Additive and Diagonal Constraints

Edit abstract data

Author(s): Krishna S, Lakshmi Manasa G and Kumar Nagaraj
Slot: Wed, 11:30-11:50, Room 22 (col. 4)

Abstract

Timed automata \cite{AD94} are a well established theoretical framework
used for modeling real time systems.
In this paper, we introduce a class of timed automata with updates
of the form $x : \sim d-y$. We show that these updates
preserve the decidability of emptiness
of classical timed automata with diagonal constraints
for $\sim \in \{=, <, \leq\}$, while
  emptiness is undecidable for $\sim \in \{>, \geq, \neq\}$.
When used along with  additive  constraints, these updates
give decidable emptiness with 2 or lesser number of clocks, and become
undecidable for 3 clocks. This provides a partial solution to a long standing
open problem \cite{BC00}.

websites: Arnold Beckmann 2008-05-18 Valid HTML 4.01! Valid CSS!