Wykorzystanie teorii automatów do przetwarzania dokumentów XML cz. II

Prelegent(ci)

Wojciech Tyczyński

Afiliacja

Uniwersytet Warszawski

Termin

3 listopada 2011 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Tematem seminarium będzie algorytm, który dla zadanego zapytania XPath \phi oraz dokumentu XMLowego t zwraca zbiór wierzchołków t, które spełniają zadaną formułę. Silniki, które zawierają algorytmy ewaluacji zapytań XPath są wbudowane we wszystkie przeglądarki internetowe. Jednakże są one tam bardzo nieefektywne - zdarza się, że ich złożoność jest wielomianem stosunkowo wysokiego stopnia względem rozmiaru dokumentu XML. W ramach seminarium zaprezentuję algorytm, który bez względu na zapytanie jest liniowy względem wielkości dokumentu, aczkolwiek nie jest już liniowy względem długości zapisu formuły XPath. Cała prezentacja jest w całości oparta na pracy doktorskiej Pawła Parysa.

---