Sun 23 Jun 2019 10:20 - 10:40 at 106C - Novel Data Applications

Cascading Style Sheets (CSS) is a popular language for describing the styles of XML documents as well as HTML documents. For a DTD D and a list R of CSS rules, due to specificity R may contain “unsatisfiable” rules under D, e.g., rules that are not applied to any element of any document valid to D. In this paper, we consider the problem of detecting unsatisfiable CSS rules under DTDs. We focus on CSS fragments in which descendant, child, adjacent sibling, and general sibling combinators are allowed. We show that the problem is coNP-hard in most cases, even if only one of the four combinators is allowed. We also show that the problem is in coNP or PSPACE depending on restrictions on DTDs and CSS. Finally, we present two conditions under which the problem can be solved in polynomial time.

Sun 23 Jun

dbpl-2019-papers
10:20 - 11:00: DBPL 2019 - Novel Data Applications at 106C
dbpl-2019-papers10:20 - 10:40
Talk
Nobutaka SuzukiUniversity of Tsukuba, Takuya OkadaUniversity of Tsukuba, Yeondae KwonThe University of Tokyo
dbpl-2019-papers10:40 - 11:00
Talk
Darshana BalakrishnanUniversity at Buffalo, Lukasz ZiarekSUNY Buffalo, USA, Oliver KennedyUniversity at Buffalo