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

Speaker(s)

Wojciech Tyczyński

Affiliation

Uniwersytet Warszawski

Date

Nov. 3, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---