Computability in Europe 2008
Logic and Theory of Algorithms

## 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\}$.
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