文献

J-GLOBAL ID：201702232478375284   整理番号：17A1965616

一般化de Bruijn系列の計算【Powered by NICT】

Computing generalized de Bruijn sequences

著者 (2件)： Blanchet-Sadri F. (Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402-6170, USA) ,  Munteanu Sinziana (Department of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213-3891, USA)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 704  ページ： 42-61  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 次数nのde Bruijn系列は,これら単語の各(実際にこれら単語の各々の正確に1つの発生を含む)の発生を含むという意味で与えられたアルファベットA上の長さnの全ての語の集合Anを表している。最近,ホールまたはしないAの各文字に適合するケア記号を持つかもしれないことを配列した部分語によるnのサブセットを表現する計算問題を考察し,NPであることが示された。しかし,Pのメンバシップをオープンに維持した。本論文では,Aの部分集合Sは部分単語によって表現可能であるかどうかを決定する入力の大きさn Sに関して多項式時間で行えることを示した。も正確に時間孔を持つ部分語による表現のための全ての整数時間を決定する多項式時間アルゴリズムを提案した。,筆者らのアルゴリズムは表現語を構築した。本手法はグラフ理論。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *単語 ,  アルゴリズム ,  グラフ理論 ,  部分集合
準シソーラス用語： 多項式時間アルゴリズム ,  多項式時間 ,  次数 , 【Automatic Indexing@JST】

著者キーワード (6件)： 語に関するアルゴリズム ,  語上の組合せ論 ,  グラフ理論 ,  部分語 ,  サブワード ,  表現可能な集合

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 一般化 ,  系列 ,  計算