Bound-decreasing duplication system

Da Jung Cho; Yo Sub Han; Hwee Kim

doi:10.1016/j.tcs.2019.06.018

Bound-decreasing duplication system

Da Jung Cho, Yo Sub Han, Hwee Kim

College of Computing

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates strings from an initial string using the bound-decreasing duplication operation. We show that there exists a nondeterministic finite-state automaton (NFA) accepting all strings generated by the bound-decreasing duplication system when an initial input is a single string; in other words, the bound-decreasing duplication system produces a regular language. This helps us to calculate the system capacity based on the corresponding NFA. Furthermore, we revisit a deduplication operation—a reverse process of duplication—on an NFA that transforms a given NFA to a smaller NFA while generating the same language by the string duplication system.

Original language	English
Pages (from-to)	152-168
Number of pages	17
Journal	Theoretical Computer Science
Volume	793
DOIs	https://doi.org/10.1016/j.tcs.2019.06.018
Publication status	Published - 2019 Nov 12

Bibliographical note

Funding Information:
We wish to thank the referees for the careful reading of the paper and many valuable suggestions. A preliminary version of this paper appeared in Proceedings of the 16th International Conference on Unconventional Computation and Natural Computation [26]. Cho was supported by Labex DigiCosme (ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program “Investissement d'Avenir” Idex Paris-Saclay (ANR-11-IDEX-0003-02), Han was supported by the Basic Science Research Program through NRF (2018R1D1A1A09084107) and Kim was supported in part by the NIH grant R01 GM109459.

Funding Information:
Cho was supported by Labex DigiCosme ( ANR-11-LABEX-0045-DIGICOSME ) operated by ANR as part of the program “Investissement d'Avenir” Idex Paris-Saclay (ANR-11-IDEX-0003-02), Han was supported by the Basic Science Research Program through NRF ( 2018R1D1A1A09084107 ) and Kim was supported in part by the NIH grant R01 GM109459 .

Publisher Copyright:
© 2019 Elsevier B.V.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/j.tcs.2019.06.018

Cite this

@article{a84ebcaaad8c418ab5f4fa319886c96a,

title = "Bound-decreasing duplication system",

abstract = "We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates strings from an initial string using the bound-decreasing duplication operation. We show that there exists a nondeterministic finite-state automaton (NFA) accepting all strings generated by the bound-decreasing duplication system when an initial input is a single string; in other words, the bound-decreasing duplication system produces a regular language. This helps us to calculate the system capacity based on the corresponding NFA. Furthermore, we revisit a deduplication operation—a reverse process of duplication—on an NFA that transforms a given NFA to a smaller NFA while generating the same language by the string duplication system.",

author = "Cho, {Da Jung} and Han, {Yo Sub} and Hwee Kim",

note = "Funding Information: We wish to thank the referees for the careful reading of the paper and many valuable suggestions. A preliminary version of this paper appeared in Proceedings of the 16th International Conference on Unconventional Computation and Natural Computation [26]. Cho was supported by Labex DigiCosme (ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program “Investissement d'Avenir” Idex Paris-Saclay (ANR-11-IDEX-0003-02), Han was supported by the Basic Science Research Program through NRF (2018R1D1A1A09084107) and Kim was supported in part by the NIH grant R01 GM109459. Funding Information: Cho was supported by Labex DigiCosme ( ANR-11-LABEX-0045-DIGICOSME ) operated by ANR as part of the program “Investissement d'Avenir” Idex Paris-Saclay (ANR-11-IDEX-0003-02), Han was supported by the Basic Science Research Program through NRF ( 2018R1D1A1A09084107 ) and Kim was supported in part by the NIH grant R01 GM109459 . Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2019",

month = nov,

day = "12",

doi = "10.1016/j.tcs.2019.06.018",

language = "English",

volume = "793",

pages = "152--168",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Bound-decreasing duplication system

AU - Cho, Da Jung

AU - Han, Yo Sub

AU - Kim, Hwee

N1 - Funding Information: We wish to thank the referees for the careful reading of the paper and many valuable suggestions. A preliminary version of this paper appeared in Proceedings of the 16th International Conference on Unconventional Computation and Natural Computation [26]. Cho was supported by Labex DigiCosme (ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program “Investissement d'Avenir” Idex Paris-Saclay (ANR-11-IDEX-0003-02), Han was supported by the Basic Science Research Program through NRF (2018R1D1A1A09084107) and Kim was supported in part by the NIH grant R01 GM109459. Funding Information: Cho was supported by Labex DigiCosme ( ANR-11-LABEX-0045-DIGICOSME ) operated by ANR as part of the program “Investissement d'Avenir” Idex Paris-Saclay (ANR-11-IDEX-0003-02), Han was supported by the Basic Science Research Program through NRF ( 2018R1D1A1A09084107 ) and Kim was supported in part by the NIH grant R01 GM109459 . Publisher Copyright: © 2019 Elsevier B.V.

PY - 2019/11/12

Y1 - 2019/11/12

N2 - We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates strings from an initial string using the bound-decreasing duplication operation. We show that there exists a nondeterministic finite-state automaton (NFA) accepting all strings generated by the bound-decreasing duplication system when an initial input is a single string; in other words, the bound-decreasing duplication system produces a regular language. This helps us to calculate the system capacity based on the corresponding NFA. Furthermore, we revisit a deduplication operation—a reverse process of duplication—on an NFA that transforms a given NFA to a smaller NFA while generating the same language by the string duplication system.

AB - We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates strings from an initial string using the bound-decreasing duplication operation. We show that there exists a nondeterministic finite-state automaton (NFA) accepting all strings generated by the bound-decreasing duplication system when an initial input is a single string; in other words, the bound-decreasing duplication system produces a regular language. This helps us to calculate the system capacity based on the corresponding NFA. Furthermore, we revisit a deduplication operation—a reverse process of duplication—on an NFA that transforms a given NFA to a smaller NFA while generating the same language by the string duplication system.

UR - http://www.scopus.com/inward/record.url?scp=85068481402&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068481402&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2019.06.018

DO - 10.1016/j.tcs.2019.06.018

M3 - Article

AN - SCOPUS:85068481402

SN - 0304-3975

VL - 793

SP - 152

EP - 168

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Bound-decreasing duplication system

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this