文献

J-GLOBAL ID：201902261369520574   整理番号：19A2817051

グラフ上の正則単純経路クエリーのためのトリコトミー【JST・京大機械翻訳】

A trichotomy for regular simple path queries on graphs

著者 (3件)： Bagan Guillaume (Universite Lyon 1, LIRIS UMR CNRS 5205, F-69622, Lyon, France) ,  Bonifati Angela (Universite Lyon 1, LIRIS UMR CNRS 5205, F-69622, Lyon, France) ,  Groz Benoit (Universite Paris Sud, LRI UMR CNRS 8623, F-91405, Orsay, France)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 108  ページ： 29-48  発行年： 2020年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 正則単純経路質問(RSPQs)の計算複雑性に焦点を合わせた。著者らは,規則的言語Lのために以下の問題RSPQ(L)を考察する。エッジラベル付き有向グラフGと2つのノードxとyは,Lに属する単語を形成するxからyへの単純な経路である。RSPQ(L)に対する追跡可能性と内部性の間のフロンティアを完全に特性化した。より正確に,RSPQ(L)は言語Lに依存してAC0,NL完全またはNP完全のいずれかであることを証明した。また,正規表現に関して扱いやすいフラグメントの簡単な特性化を提供した。最後に,言語Lが上記のフラグメントに属するかどうかを決定する複雑さを論じた。L:DFAs,NFAsまたは正規表現のいくつかの代替表現を考察し,この問題が最初の表現に対してNL完全であり,他の2つに対してPS_PACE完全であることを証明した。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 有向グラフ ,  *正規表現 ,  計算量 ,  キャラクタリゼーション ,  言語 ,  単語 ,  オートマトン ,  トレーサビリティ
準シソーラス用語： 複雑性 ,  NP完全性 ,  *クエリー , 【Automatic Indexing@JST】

著者キーワード (6件)： グラフ ,  パス ,  正則単純経路 ,  複雑さ ,  正則言語 ,  オートマトン

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (3件)： グラフ ,  経路 ,  クエリー