Tenth and final Meeting
- Oded Maler (VERIMAG)
-
Title: On Recognizable Timed Languages (Slides)
- Abstract:
In this work we generalize the fundamental notion of recognizability
from untimed to timed languages. The essence of our definition is the
existence of a right-morphism from the monoid of timed words into a
bounded subset of itself. We show that the recognizable
languages are exactly those accepted by deterministic timed automata
and argue that this is, perhaps, the right class of timed languages,
and that the closure of untimed regular languages under projection is
a positive accident that cannot be expected to hold beyond the
finite-state case.
(Joint work with Amir Pnueli)