Complexity of Finding Alphabet Indexing
スポンサーリンク
概要
- 論文の詳細を見る
For two finite disjoint sets P and Q of strings over an alphabet Σ, an alphabet indexing ψ for P, Q by an indexing alphabet Γ with |Γ| < |Γ| is a mapping ψ : Σ → Γ satisfying ψ(P) ∩ ψ(Q) = ∅, where ψ : Σ → Γ is the homomorphism derived from ψ. 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.
- 社団法人電子情報通信学会の論文
- 1995-01-25
著者
-
Miyano Satoru
Research Institute Of Fundamental Information Science Faculty Of Science Kyushu University
-
Shimozono Shinichi
Department Of Artificial Intelligence Kyushu Institute Of Technology
-
Shimozono Shinichi
Department Of Control Engineering And Science Kyushu Institute Of Technology
関連論文
- Knowledge Acquisition from Amino Sequences by Machine Learning System BONSAI
- Hardness Results on Local Multiple Alignment of Biological Sequences
- Learning Theory Toward Genome Informatics
- A New Series of $\Delta^p_2$-Complete Problems
- Systematized Approaches to the Complexity of Subgraph Problems
- Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
- Using Maximal Independent Sets to Solve Problems in Parallel
- O(log^* n) Time Parallel Algorithm for Computing Bounded degree Maximal Subgraphs
- A Parallel Algorithm for the Maximal Co-Hitting Set Problem
- O(log^* n) Time Parallel Algorithm for Computing Bounded Degree Maximal Subgraphs
- Complexity of Finding Alphabet Indexing
- O(log^* n) Time Parallel Algorithm for Computing Bounded Degree Maximal Subgraphs
- Hardness Results on Local Multiple Alignment of Biological Sequences