Efficient evaluation for temporal logic on changing XML documents joint work with Diego Figueira

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

8 grudnia 2010 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We consider a sequence $t_1,\ldots,t_k$ of XML documents that is
produced by a sequence of local edit operations. To describe
properties of such a sequence, we use a temporal logic. The logic can
navigate both in time and in the document, e.g.~a formula can say that
every node with label $a$ eventually gets a descendant with label $b$.
For every fixed formula, we provide an evaluation algorithm that works
in time $O(k \cdot \log(n))$, where $k$ is the number of edit
operations and $n$ is the maximal size of document that is produced.
In the algorithm, we  represent of  formulas of the logic by a kind of
automaton, which works on sequences of documents.

---