IEICE TRANSACTIONS on Information
On CSS Unsatisfiability Problem in the Presense of DTDs
Summary :
Cascading Style Sheets (CSS) is a popular language for describing the styles of XML documents as well as HTML documents. To resolve conflicts among CSS rules, CSS has a mechanism called specificity. For a DTD D and a CSS code R, due to specificity R may contain “unsatisfiable” rules under D, e.g., rules that are not applied to any element of any document valid for 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 and under very restricted DTDs. We also show that the problem is in coNP or PSPACE depending on restrictions on DTDs and CSS. Finally, we present four conditions under which the problem can be solved in polynomial time.
- Publication
- IEICE TRANSACTIONS on Information Vol.E104-D No.6 pp.801-815
- Publication Date
- 2021/06/01
- Publicized
- 2021/03/10
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021EDP7002
- Type of Manuscript
- PAPER
- Category
- Data Engineering, Web Information Systems
Authors
Nobutaka SUZUKI
University of Tsukuba
Takuya OKADA
Nihon Unisys, Ltd
Yeondae KWON
University of Tokyo
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Nobutaka SUZUKI, Takuya OKADA, Yeondae KWON, "On CSS Unsatisfiability Problem in the Presense of DTDs" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 6, pp. 801-815, June 2021, doi: 10.1587/transinf.2021EDP7002.
Abstract: Cascading Style Sheets (CSS) is a popular language for describing the styles of XML documents as well as HTML documents. To resolve conflicts among CSS rules, CSS has a mechanism called specificity. For a DTD D and a CSS code R, due to specificity R may contain “unsatisfiable” rules under D, e.g., rules that are not applied to any element of any document valid for 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 and under very restricted DTDs. We also show that the problem is in coNP or PSPACE depending on restrictions on DTDs and CSS. Finally, we present four conditions under which the problem can be solved in polynomial time.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7002/_p
Copy
@ARTICLE{e104-d_6_801,
author={Nobutaka SUZUKI, Takuya OKADA, Yeondae KWON, },
journal={IEICE TRANSACTIONS on Information},
title={On CSS Unsatisfiability Problem in the Presense of DTDs},
year={2021},
volume={E104-D},
number={6},
pages={801-815},
abstract={Cascading Style Sheets (CSS) is a popular language for describing the styles of XML documents as well as HTML documents. To resolve conflicts among CSS rules, CSS has a mechanism called specificity. For a DTD D and a CSS code R, due to specificity R may contain “unsatisfiable” rules under D, e.g., rules that are not applied to any element of any document valid for 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 and under very restricted DTDs. We also show that the problem is in coNP or PSPACE depending on restrictions on DTDs and CSS. Finally, we present four conditions under which the problem can be solved in polynomial time.},
keywords={},
doi={10.1587/transinf.2021EDP7002},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - On CSS Unsatisfiability Problem in the Presense of DTDs
T2 - IEICE TRANSACTIONS on Information
SP - 801
EP - 815
AU - Nobutaka SUZUKI
AU - Takuya OKADA
AU - Yeondae KWON
PY - 2021
DO - 10.1587/transinf.2021EDP7002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2021
AB - Cascading Style Sheets (CSS) is a popular language for describing the styles of XML documents as well as HTML documents. To resolve conflicts among CSS rules, CSS has a mechanism called specificity. For a DTD D and a CSS code R, due to specificity R may contain “unsatisfiable” rules under D, e.g., rules that are not applied to any element of any document valid for 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 and under very restricted DTDs. We also show that the problem is in coNP or PSPACE depending on restrictions on DTDs and CSS. Finally, we present four conditions under which the problem can be solved in polynomial time.
ER -
English
