文献

J-GLOBAL ID：201702219983527615   整理番号：17A1965589

部分語と不確定なストリングのための被覆問題【Powered by NICT】

Covering problems for partial words and for indeterminate strings

著者 (8件)： Crochemore Maxime (Department of Informatics, King’s College London, UK) ,  Crochemore Maxime (Universite Paris-Est, France) ,  Iliopoulos Costas S. (Department of Informatics, King’s College London, UK) ,  Kociumaka Tomasz (Institute of Informatics, University of Warsaw, Poland) ,  Radoszewski Jakub (Department of Informatics, King’s College London, UK) ,  Radoszewski Jakub (Institute of Informatics, University of Warsaw, Poland) ,  Rytter Wojciech (Institute of Informatics, University of Warsaw, Poland) ,  Walen Tomasz (Institute of Informatics, University of Warsaw, Poland)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 698  ページ： 25-39  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 不確定ストリングは非決定論的性質を持つ非標準語のサブクラスである。古典ストリングにおいては,すべての位置が不確定なストリングにおける位置は記号の集合を含む可能性がある(この位置で可能)記号が,固体すなわちシンボル,正確に1つを含んでいる;そのような集合は非記号と呼ばれている。不確定ストリングの最も重要なサブクラスは部分語,各非記号は全アルファベットであるこの場合の非記号もケアシンボルないと呼ばれている。無限ストリングの最短被覆を見出し,その発生は全不確定ストリングをカバーする最短固体ストリングを見出す問題を考察した。はこの古典的問題は不確定なストリングと部分語に対してもNP完全になることを示した。この事実の証明が本稿の主要結果の一つである。著者らの他の主要な結果は,最短被覆問題のための入力のある種のパラメータに関して効率的な(いわゆるFPTアルゴリズム)アルゴリズムの設計に焦点を当てた。不確定ストリング被覆問題のために,O(n k 2 +2 k k 3)時間アルゴリズム,kは非記号数を得るために,部分単語被覆問題のためのO(n K二二零(k logk))の走行時間を得る。,指数時間仮説偽なければ,二零(K)n O(1)時間解は問題のための存在しないことを証明し,これは部分語のための著者らのアルゴリズムは,最適に近いことを示した。もKの両方によってパラメータ化された両問題と簡単な実施によりアルファベットサイズのためのアルゴリズムを提案した。本論文の準備版は[1]アルゴリズムと計算(ISAAC 2014),LNCS,volに関する第二十五回国際シンポジウムで提示した。8889pp.220 232Springer(2014)。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *被覆問題 ,  計算 ,  アルゴリズム ,  単語 ,  *被覆 ,  パラメタリゼーション ,  走行時間 ,  *不確実性
準シソーラス用語： アルゴリズム設計 , 【Automatic Indexing@JST】

著者キーワード (5件)： 単語の被覆 ,  部分単語 ,  ドントケアによるストリング ,  不確定なストリング ,  固定パラメータ実行可能性

分類 (2件)： 計算理論  (JB02000A) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (1件)： 被覆問題