## ＜テクニカルレポート＞Complexity of Finding Alphabet Indexing

作成者 作成者名 所属機関 所属機関名 Department of Control Engineering and Science, Kyushu Institute of Technology 著者識別子 作成者名 所属機関 所属機関名 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1992-08 61 Accepted Manuscript open access For two finite disjoint sets $P$ and $Q$ of strings over an alphabet $sum$, an alphabet indexing $psi$ for $P,Q$ by an indexing alphabet $Gamma$ with $mid Gamma mid < mid sum mid is a mapping$psi : ...sum \to Gamma$satisfying$\tilde{psi}(P) cap \tilde{psi}(Q) = emptyset$, where$\tilde{psi} : sum^* \to Gamma^*$is the homomorphism derived from$psi\$. We defined this notion through experiments of knowledge acquisition from amino acid sequences of proteins by learning algorithms. This paper analyzes the complexity of finding an alphabet indexing. We first show that the problem is NP-complete. Then we give a local search algorithm for this problem and show a result on PLS-completeness.続きを見る

### 本文情報を非表示

61.ps tgz 51.1 KB 9
61.ps.tar pdf 177 KB 93

### 詳細

レコードID 3066 査読無 RIFIS Technical Report || 61 http://www.i.kyushu-u.ac.jp/research/report.html Algorithm and Computational Complexity Alphabet Indexing Local Search Algorithm NP-Complete PLS-Complete テクニカルレポート 2009.04.22 2018.08.31