Nie jesteś zalogowany | Zaloguj się

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.