<テクニカルレポート>
Complexity of Finding Alphabet Indexing

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 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 6  
61.ps.tar pdf 177 KB 91  

詳細

レコードID
査読有無
関連情報
主題
タイプ
登録日 2009.04.22
更新日 2017.01.20