Which data words are simple from an XPath perspective?

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

30 maja 2012 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Vince Barany, Diego Figueira, Paweł Parys

Seminarium

Seminarium „Teoria automatów”

---

XPath satisfiability is undecidable. However, when doing the
undecidability proof, one produces formulas that are only satisfied by
very artificial data words. We propose a measure of data words,
emulating tree-width for graphs, such that the following problem is
decidable: given a number k, and an Xpath formula phi, decide if the
formula is satisfied in a data word of measure at most k.

---