| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
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.続きを見る
|
Mendeley出力
