Outfix-guided insertion

Da Jung Cho; Yo Sub Han; Timothy Ng; Kai Salomaa

doi:10.1016/j.tcs.2017.03.040

Outfix-guided insertion

Da Jung Cho, Yo Sub Han, Timothy Ng, Kai Salomaa

College of Computing

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

6 Citations (Scopus)

Abstract

Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is non-regular. We consider also the closure properties of regular and (deterministic) context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time. The complexity of the corresponding question for nondeterministic finite automata remains open.

Original language	English
Pages (from-to)	70-84
Number of pages	15
Journal	Theoretical Computer Science
Volume	701
DOIs	https://doi.org/10.1016/j.tcs.2017.03.040
Publication status	Published - 2017 Nov 21

Bibliographical note

Funding Information:
We thank the referees for many useful suggestions that have improved the presentation of the paper. Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST ( 2015R1D1A1A01060097 ), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government ( MSIP ) ( R0124-16-0002 ). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224 .

Funding Information:
We thank the referees for many useful suggestions that have improved the presentation of the paper. Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

Publisher Copyright:
© 2017 Elsevier B.V.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/j.tcs.2017.03.040

Cite this

@article{209f7f81a1f047f9b0ac871ea0009f4b,

title = "Outfix-guided insertion",

abstract = "Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is non-regular. We consider also the closure properties of regular and (deterministic) context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time. The complexity of the corresponding question for nondeterministic finite automata remains open.",

author = "Cho, {Da Jung} and Han, {Yo Sub} and Timothy Ng and Kai Salomaa",

note = "Funding Information: We thank the referees for many useful suggestions that have improved the presentation of the paper. Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST ( 2015R1D1A1A01060097 ), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government ( MSIP ) ( R0124-16-0002 ). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224 . Funding Information: We thank the referees for many useful suggestions that have improved the presentation of the paper. Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = nov,

day = "21",

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

language = "English",

volume = "701",

pages = "70--84",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Outfix-guided insertion

AU - Cho, Da Jung

AU - Han, Yo Sub

AU - Ng, Timothy

AU - Salomaa, Kai

N1 - Funding Information: We thank the referees for many useful suggestions that have improved the presentation of the paper. Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST ( 2015R1D1A1A01060097 ), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government ( MSIP ) ( R0124-16-0002 ). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224 . Funding Information: We thank the referees for many useful suggestions that have improved the presentation of the paper. Cho and Han were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future-leading Research Initiative of 2016 and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. Publisher Copyright: © 2017 Elsevier B.V.

PY - 2017/11/21

Y1 - 2017/11/21

N2 - Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is non-regular. We consider also the closure properties of regular and (deterministic) context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time. The complexity of the corresponding question for nondeterministic finite automata remains open.

AB - Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is non-regular. We consider also the closure properties of regular and (deterministic) context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time. The complexity of the corresponding question for nondeterministic finite automata remains open.

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

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

U2 - 10.1016/j.tcs.2017.03.040

DO - 10.1016/j.tcs.2017.03.040

M3 - Article

AN - SCOPUS:85018622026

SN - 0304-3975

VL - 701

SP - 70

EP - 84

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Outfix-guided insertion

Abstract

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this