講演抄録/キーワード |
講演名 |
2008-12-19 11:15
木オートマトンを用いたXML処理 ○高田喜朗(高知工科大)・関 浩之(奈良先端大) SS2008-46 |
抄録 |
(和) |
木オートマトンは,文字列に対する有限オートマトンを木に対して拡張した計算モデルであり,与えられた木に対して「受理」か「拒否」かを出力する形式言語理論上の道具である.古くから様々な応用分野で研究されてきたが,近年ではXML文書処理への応用もよく研究されている.特に,DTD%, W3C XML Schema, RELAX NG等で定義されたスキーマ(文書構造定義)は木オートマトンで自然にモデル化でき,スキーマ適合性判定問題を容易に取り扱える.また,XSLT等で記述されたXML文書変換やXQuery等で記述された問い合わせのモデルとして,木オートマトンの拡張である木変換器やその拡張がよく用いられる.
本稿では,木オートマトンや木変換器を用いたXML文書処理技術について,基本的な概念や手法を紹介する.また,XML処理のための木オートマトンに基づくモデルを扱っている研究例を簡単にまとめて紹介する. |
(英) |
Tree automata, which are finite automata over trees, have been investigated in various research areas for a long time. A recent example of such work is the application to XML processing. In particular, a schema specified in a well-known schema description language such as DTD is naturally modeled as a tree automaton, and the problem of checking the validity of XML document(s) for schema can be reduced to the membership problem for tree automata.
Finite state tree transducers, which are extensions of tree automata that translate input trees into output trees, have been used for a model of XML transformation and XML query.
In this paper, we give an introduction to and a brief summery on the tree automata-based
XML processing. |
キーワード |
(和) |
XML / 木オートマトン / 形式言語理論 / 木変換器 / 型検査 / / / |
(英) |
XML / Tree automaton / Formal language theory / Tree transducer / Type checking / / / |
文献情報 |
信学技報, vol. 108, no. 362, SS2008-46, pp. 43-50, 2008年12月. |
資料番号 |
SS2008-46 |
発行日 |
2008-12-11 (SS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
SS2008-46 |