Nie jesteś zalogowany |
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
- 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.
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.
