Query Width

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

9 grudnia 2009 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Slawomir Lasota

Seminarium

Seminarium „Teoria automatów”

---

Query Width is a complexity measure, like Tree Width, or Clique Width. The difference is that Tree Width or Clique Width measure the complexity of a graph, while Query Width measures the complexity of a graph whose nodes are linearly ordered (or organized in a tree, in the more general case). I will discuss where this notion comes from (our research on XPath), how it is related to the other measures (closely, with clique width) and what can be done in the future.

---