Tableaux for Hybrid XPath with Data

C. Areces, R. Fervari, and N. Seiler. Tableaux for Hybrid XPath with Data. In Progress in Artificial Intelligence - 18th EPIA Conference on Artificial Intelligence, EPIA 2017, Porto, Portugal, September 5-8, 2017, Proceedings, pp. 611–623, 2017.

Download

[pdf] 

Abstract

We provide a sound, complete and terminating tableau procedure to check satisfiability of downward XPath= formulas enriched with nominals and satisfaction operators. The calculus is inspired by ideas introduced to ensure termination of tableau calculi for certain Hybrid Logics. We prove that even though we increased the expressive power of XPath by introducing hybrid operators, the satisfiability problem for the obtained logic is still PSpace-complete.

BibTeX

@InCollection{Areces2017a,
  author =       "C. Areces and R. Fervari and N. Seiler",
  booktitle =    "Progress in Artificial Intelligence - 18th {EPIA}
                 Conference on Artificial Intelligence, {EPIA} 2017,
                 Porto, Portugal, September 5-8, 2017, Proceedings",
  title =        "Tableaux for Hybrid {XP}ath with Data",
  year =         "2017",
  pages =        "611--623",
  abstract =     "We provide a sound, complete and terminating tableau
                 procedure to check satisfiability of downward XPath=
                 formulas enriched with nominals and satisfaction
                 operators. The calculus is inspired by ideas introduced
                 to ensure termination of tableau calculi for certain
                 Hybrid Logics. We prove that even though we increased
                 the expressive power of XPath by introducing hybrid
                 operators, the satisfiability problem for the obtained
                 logic is still PSpace-complete.",
  bibsource =    "dblp computer science bibliography, https://dblp.org",
  biburl =       "https://dblp.org/rec/conf/epia/ArecesFS17.bib",
  doi =          "10.1007/978-3-319-65340-2\_50",
  timestamp =    "Tue, 14 May 2019 10:00:41 +0200",
  URL =          "https://doi.org/10.1007/978-3-319-65340-2\_50",
  ISBN =         "978-3-319-65339-6",
}