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

Displayed time zone: Tijuana, Baja California change

10:20 - 11:00
Novel Data ApplicationsDBPL at 106C
10:20
20m
Talk
Detecting Unsatisfiable CSS Rules in the Presence of DTDs
DBPL
Nobutaka Suzuki University of Tsukuba, Takuya Okada University of Tsukuba, Yeondae Kwon The University of Tokyo
10:40
20m
Talk
Fluid Data Structures
DBPL
Darshana Balakrishnan University at Buffalo, Lukasz Ziarek SUNY Buffalo, USA, Oliver Kennedy University at Buffalo