You are not logged in |
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
- 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.
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.
