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

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

May 30, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

Which data words are simple from an XPath perspective?

Seminar

Seminar Automata Theory

---

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.

---