Complexity of Finding Alphabet Indexing

Shinichi SHIMOZONO  Satoru MIYANO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.1   pp.13-18
Publication Date: 1995/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
algorithm and computational complexity,  alphabet indexing,  local search algorithm,  NP-complete,  PLS-complete,  

Full Text: PDF>>
Buy this Article




Summary: 
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.