Query Width
- Prelegent(ci)
- Mikołaj Bojańczyk
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 9 grudnia 2009 14:15
- Pokój
- p. 5870
- 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.