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

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Dec. 8, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---