Deduplication on finite automata and nested duplication systems

Da Jung Cho; Yo Sub Han; Hwee Kim

doi:10.1007/978-3-319-58187-3_15

Deduplication on finite automata and nested duplication systems

Da Jung Cho, Yo Sub Han, Hwee Kim

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

Motivated by work on bio-operations on DNA sequences, a string duplication system S consists of an initial string over Σ and a set of duplication functions that iteratively generate new strings from existing strings in the system. As the main result we introduce the concept of a deduplication—a reverse function of duplication—on an nondeterministic finite-state automaton (NFA) and propose the deduplication operation on an NFA that transforms a given NFA to a smaller NFA while generating the same language in the string duplication system. Then, we introduce a nested duplication, which is similar to tandem duplication but depends on the information of the nested duplication in the previous step. We propose an NFA construction for an arbitrary nested duplication system, analyze its properties and present an algorithm that computes the system capacity.

Original language	English
Title of host publication	Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings
Editors	Matthew J. Patitz, Mike Stannett
Publisher	Springer Verlag
Pages	194-205
Number of pages	12
ISBN (Print)	9783319581866
DOIs	https://doi.org/10.1007/978-3-319-58187-3_15
Publication status	Published - 2017
Event	16th International Conference on Unconventional Computation and Natural Computation, UCNC 2017 - Fayetteville, United States Duration: 2017 Jun 5 → 2017 Jun 9

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10240 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th International Conference on Unconventional Computation and Natural Computation, UCNC 2017
Country/Territory	United States
City	Fayetteville
Period	17/6/5 → 17/6/9

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG 2017.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-58187-3_15

Cite this

Cho, D. J., Han, Y. S., & Kim, H. (2017). Deduplication on finite automata and nested duplication systems. In M. J. Patitz, & M. Stannett (Eds.), Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings (pp. 194-205). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10240 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-58187-3_15

Cho, Da Jung ; Han, Yo Sub ; Kim, Hwee. / Deduplication on finite automata and nested duplication systems. Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings. editor / Matthew J. Patitz ; Mike Stannett. Springer Verlag, 2017. pp. 194-205 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7e5d4d99523e425c83a52de2727e18ca,

title = "Deduplication on finite automata and nested duplication systems",

abstract = "Motivated by work on bio-operations on DNA sequences, a string duplication system S consists of an initial string over Σ and a set of duplication functions that iteratively generate new strings from existing strings in the system. As the main result we introduce the concept of a deduplication—a reverse function of duplication—on an nondeterministic finite-state automaton (NFA) and propose the deduplication operation on an NFA that transforms a given NFA to a smaller NFA while generating the same language in the string duplication system. Then, we introduce a nested duplication, which is similar to tandem duplication but depends on the information of the nested duplication in the previous step. We propose an NFA construction for an arbitrary nested duplication system, analyze its properties and present an algorithm that computes the system capacity.",

keywords = "Automata theory, Bio-inspired operations, Capacity, String duplication systems, Tandem duplication",

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

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 16th International Conference on Unconventional Computation and Natural Computation, UCNC 2017 ; Conference date: 05-06-2017 Through 09-06-2017",

year = "2017",

doi = "10.1007/978-3-319-58187-3_15",

language = "English",

isbn = "9783319581866",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "194--205",

editor = "Patitz, {Matthew J.} and Mike Stannett",

booktitle = "Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings",

address = "Germany",

}

Cho, DJ, Han, YS & Kim, H 2017, Deduplication on finite automata and nested duplication systems. in MJ Patitz & M Stannett (eds), Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10240 LNCS, Springer Verlag, pp. 194-205, 16th International Conference on Unconventional Computation and Natural Computation, UCNC 2017, Fayetteville, United States, 17/6/5. https://doi.org/10.1007/978-3-319-58187-3_15

Deduplication on finite automata and nested duplication systems. / Cho, Da Jung; Han, Yo Sub; Kim, Hwee.
Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings. ed. / Matthew J. Patitz; Mike Stannett. Springer Verlag, 2017. p. 194-205 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10240 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Deduplication on finite automata and nested duplication systems

AU - Cho, Da Jung

AU - Han, Yo Sub

AU - Kim, Hwee

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - Motivated by work on bio-operations on DNA sequences, a string duplication system S consists of an initial string over Σ and a set of duplication functions that iteratively generate new strings from existing strings in the system. As the main result we introduce the concept of a deduplication—a reverse function of duplication—on an nondeterministic finite-state automaton (NFA) and propose the deduplication operation on an NFA that transforms a given NFA to a smaller NFA while generating the same language in the string duplication system. Then, we introduce a nested duplication, which is similar to tandem duplication but depends on the information of the nested duplication in the previous step. We propose an NFA construction for an arbitrary nested duplication system, analyze its properties and present an algorithm that computes the system capacity.

AB - Motivated by work on bio-operations on DNA sequences, a string duplication system S consists of an initial string over Σ and a set of duplication functions that iteratively generate new strings from existing strings in the system. As the main result we introduce the concept of a deduplication—a reverse function of duplication—on an nondeterministic finite-state automaton (NFA) and propose the deduplication operation on an NFA that transforms a given NFA to a smaller NFA while generating the same language in the string duplication system. Then, we introduce a nested duplication, which is similar to tandem duplication but depends on the information of the nested duplication in the previous step. We propose an NFA construction for an arbitrary nested duplication system, analyze its properties and present an algorithm that computes the system capacity.

KW - Automata theory

KW - Bio-inspired operations

KW - Capacity

KW - String duplication systems

KW - Tandem duplication

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

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

U2 - 10.1007/978-3-319-58187-3_15

DO - 10.1007/978-3-319-58187-3_15

M3 - Conference contribution

AN - SCOPUS:85020314542

SN - 9783319581866

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 194

EP - 205

BT - Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings

A2 - Patitz, Matthew J.

A2 - Stannett, Mike

PB - Springer Verlag

T2 - 16th International Conference on Unconventional Computation and Natural Computation, UCNC 2017

Y2 - 5 June 2017 through 9 June 2017

ER -

Cho DJ, Han YS, Kim H. Deduplication on finite automata and nested duplication systems. In Patitz MJ, Stannett M, editors, Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Proceedings. Springer Verlag. 2017. p. 194-205. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-58187-3_15

Deduplication on finite automata and nested duplication systems

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this