Complexity of Finding Alphabet Indexing

Shinichi SHIMOZONO; Satoru MIYANO

Complexity of Finding Alphabet Indexing

Shinichi SHIMOZONO, Satoru MIYANO

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E78-D No.1 pp.13-18

Publication Date: 1995/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Cite this

Copy

Shinichi SHIMOZONO, Satoru MIYANO, "Complexity of Finding Alphabet Indexing" in IEICE TRANSACTIONS on Information, vol. E78-D, no. 1, pp. 13-18, January 1995, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e78-d_1_13/_p

Copy

@ARTICLE{e78-d_1_13,
author={Shinichi SHIMOZONO, Satoru MIYANO, },
journal={IEICE TRANSACTIONS on Information},
title={Complexity of Finding Alphabet Indexing},
year={1995},
volume={E78-D},
number={1},
pages={13-18},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Complexity of Finding Alphabet Indexing
T2 - IEICE TRANSACTIONS on Information
SP - 13
EP - 18
AU - Shinichi SHIMOZONO
AU - Satoru MIYANO
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1995
AB - 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.
ER -