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

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.