著者

中村 有作 舞田 哲哉 坂本 比呂志

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.22, no.2, pp.191-199, 2007 (Released:2007-01-25)

参考文献数

29

---

We propose an efficient algorithm for deciding the reachability between any nodes on XML data represented by connected directed graphs. We develop a technique to reduce the size of the reference table for the reachability test. Using the small table and the standard range labeling method for rooted ordered trees, we show that our algorithm answers almost queries in a constant time preserving the space efficiency and a reasonable preprocessing time.