半構造データ上では その構造が不規則なので 与えられた経路式により適切な探索が行われるかどうかは必ずしも明解でない.本論文では 次のような理由から 経路式peより探索される経路の中で最短のもの すなわち peを満たす最短経路を求めるアルゴリズムを考える(I)peを満たす経路を確認できれば peの働きが適切かどうかを検証できる.(ii)このような検証のためには peを満たす経路の中で(無駄な頂点や辺を迂回しない)より短い経路の方が適している.このアルゴリズムを 次の定式化の下で構成する: (i)半構造データを重み付き有向グラフで表す.(ii)経路式として正則表現及び文脈自由文法(CFG)を用いる.Rを正則表現 GcfをCFG mを正整数とする.本論文では 以下の3つの結果を示す.まず すべての頂点対(u v)に対してuからvへのRを満たす最短経路を求める多項式時間アルゴリズムを示す.次に すべての頂点対(u v)に対してuからvへのGcfを満たす最短経路を求めるアルゴリズムを示す.最後に すべての頂点対(u v)に対して(i)uからvへの重みがm以下のGcfを満たす経路があるかどうかを決定し (ii)もしそのような経路が存在するならば uからvへのGcfを満たす最短経路を求めるアルゴリズムを示す.このアルゴリズムは 各辺の重みが1以上の場合 疑似多項式時間で動作する.Over semistructured data, due to the irregularity it tends to be unclear if a given path expression retrieves appropriately. In this paper, we consider algorithms that find shortest paths retreieved by a given path expression pe (i.e. shortest paths satisfying pe)for the following reason: (i)whether pe retrieves appropriately can be verified by checking paths satisfying pe and (ii) for such a verification ,paths containing less vertices/edges are more desirable. We construct the algorithms in following context: (i) semistructured data is modeled by a weighted labeled directed graph and (ii) a path expression is represented by a regular expression or a context-free grammar (CFG). Let R be a regular expression, Gcf be a CFG ,and m be a positive integer. In this paper, we present the following three results. First, we present the following three results. First, we present a polynomial-time algorithm that finds a shortest path satisfying R from u to v for every pair of nodes u and v. Second, we present an algorithm that finds a shortest path satisfying Gcf from u to v for every pair of nodes u and v. Finally, we present an algorithm that decides for every pair of nodes u and v (i) whether there is a path p satisfying Gcf from u to v such that w(p)≦m and (ii)if such a path exists, then also finds a shortest satisfying Gcf from u to v. The decision algorithm runs in pseudopolynomial time if every weight is positive.
