The monitoring problem for timed automata

Prelegent(ci)

Filip Mazowiecki

Afiliacja

MPI SWS

Termin

6 maja 2020 14:15

Informacje na temat wydarzenia

Online seminar

Tytuł w języku angielskim

joint work with Alejandro Grez, Michał Pilipczuk, Gabriele Puppis and Cristian Riveros

Seminarium

Seminarium „Teoria automatów”

---

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a different perspective, that is, we consider a dynamic version of the problem, called monitoring problem, where the automaton is fixed and the input is revealed as in a stream, one symbol at a time following the natural order on positions. The goal here is to design a dynamic data structure that can be queried about whether the word consisting of symbols revealed so far is accepted by the automaton, and that can be efficiently updated when the next symbol is revealed. We provide complexity bounds for this monitoring problem, by considering timed automata that process symbols interleaved with timestamps. The main contribution is that monitoring of a one-clock timed automaton, with all its components but the clock constants fixed, can be done in amortised constant time per input symbol.

 

This work is available on arxiv https://arxiv.org/abs/2002.07049.

---