joint work with Slawomir Lasota

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Dec. 9, 2009, 2:15 p.m.

Room

room 5870

Title in Polish

Query Width

Seminar

Seminar Automata Theory

---

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.

---