グラフデータースにおける正則表現及び文脈自由文法を満たす最短経路の?探索法

• Item type: Trans(1)
• 公開日: 1999-08-15
• タイトル: グラフデータースにおける正則表現及び文脈自由文法を満たす最短経路の?探索法
• タイトル / 言語: en
• タイトル: Finding Shortest Paths Satisfying Regular Expressions
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 岡山県立大学情報工学部
• 著者所属: 岡山県立大学情報工学部
• 著者所属: 岡山県立大学情報工学部
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Okayama Prefectural University
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Okayama Prefectural University
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Okayama Prefectural University
• 著者名: 鈴木, 伸崇; 佐藤洋一郎; 早瀬, 道芳
• 著者名(英): Nobutaka, Suzuki; Yoichirou, Sato; Michiyoshi, Hayase
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 半構造データ上では その構造が不規則なので 与えられた経路式により適切な探索が行われるかどうかは必ずしも明解でない.本論文では 次のような理由から 経路式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以上の場合 疑似多項式時間で動作する.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 40, 号 SIG06(TOD3), p. 42-53, 発行日 1999-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会