講演抄録/キーワード |
講演名 |
2012-03-14 09:25
Combining the tractability of duplicate-free DTDs and disjunction-capsuled DTDs for XPath satisfiability with sibling axes ○Yasunori Ishihara(Osaka Univ.)・Shogo Shimizu(AIIT)・Kenji Hashimoto(NAIST)・Toru Fujiwara(Osaka Univ.) SS2011-76 |
抄録 |
(和) |
本稿では,子軸,子孫軸および兄弟軸をもつXPath充足可能性問題が効率よく解けるような,
DTDの新たな部分クラスDC/DF-DTDを示す.
DC/DF-DTDは,効率よく解けることが知られている
duplicate-free DTDおよびdisjunction-capsuled DTDのクラスの
「混成物」として定義され,
正規表現に``?''(0回または1回の出現)や
``+''(1回以上の出現)の演算を許さないという制限のもとでは
それら既知のクラスを真に含む.
本稿では,親軸や述語を含むXPathクラスに対しては,
DC/DF-DTDのもとでの充足可能性問題が手に負えなくなることも示す. |
(英) |
This paper demonstrates a new subclass of DTDs,
called DC/DF-DTDs, under which XPath
satisfiability with child, descendant-or-self, and
sibling axes becomes tractable.
DC/DF-DTDs are defined as a ``hybrid'' of two known tractable classes,
duplicate-free DTDs and disjunction-capsuled DTDs,
and are a proper superclass of them,
provided that operators ``?'' (zero or one occurrence) and
``+'' (one or more occurrences) are disallowed.
This paper also shows that parent axes or qualifiers bring
intractability to XPath satisfiability under DC/DF-DTDs. |
キーワード |
(和) |
XPath / 充足可能性 / 計算量 / / / / / |
(英) |
XPath / satisfiability / complexity / / / / / |
文献情報 |
信学技報, vol. 111, no. 481, SS2011-76, pp. 115-120, 2012年3月. |
資料番号 |
SS2011-76 |
発行日 |
2012-03-06 (SS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
SS2011-76 |