Outfix-guided insertion

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

doi:10.1007/978-3-662-53132-7_9

Outfix-guided insertion

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

College of Computing

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

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 nonregular. 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.

Original language	English
Title of host publication	Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings
Editors	Christophe Reutenauer, Srecko Brlek
Publisher	Springer Verlag
Pages	102-113
Number of pages	12
ISBN (Print)	9783662531310
DOIs	https://doi.org/10.1007/978-3-662-53132-7_9
Publication status	Published - 2016
Event	20th International Conference on Developments in Language Theory, DLT 2016 - Montreal, Canada Duration: 2016 Jul 25 → 2016 Jul 28

Publication series

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

Other

Other	20th International Conference on Developments in Language Theory, DLT 2016
Country/Territory	Canada
City	Montreal
Period	16/7/25 → 16/7/28

Bibliographical note

Funding Information:
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 2015 and the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-662-53132-7_9

Cite this

Cho, D. J., Han, Y. S., Ng, T., & Salomaa, K. (2016). Outfix-guided insertion. In C. Reutenauer, & S. Brlek (Eds.), Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings (pp. 102-113). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9840). Springer Verlag. https://doi.org/10.1007/978-3-662-53132-7_9

Cho, Da Jung ; Han, Yo Sub ; Ng, Timothy et al. / Outfix-guided insertion. Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings. editor / Christophe Reutenauer ; Srecko Brlek. Springer Verlag, 2016. pp. 102-113 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{378ca16777f145f19ab40593c8d6bd3c,

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 nonregular. 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.",

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

note = "Funding Information: 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 2015 and the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 20th International Conference on Developments in Language Theory, DLT 2016 ; Conference date: 25-07-2016 Through 28-07-2016",

year = "2016",

doi = "10.1007/978-3-662-53132-7_9",

language = "English",

isbn = "9783662531310",

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

publisher = "Springer Verlag",

pages = "102--113",

editor = "Christophe Reutenauer and Srecko Brlek",

booktitle = "Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings",

address = "Germany",

}

Cho, DJ, Han, YS, Ng, T & Salomaa, K 2016, Outfix-guided insertion. in C Reutenauer & S Brlek (eds), Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9840, Springer Verlag, pp. 102-113, 20th International Conference on Developments in Language Theory, DLT 2016, Montreal, Canada, 16/7/25. https://doi.org/10.1007/978-3-662-53132-7_9

Outfix-guided insertion. / Cho, Da Jung; Han, Yo Sub; Ng, Timothy et al.
Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings. ed. / Christophe Reutenauer; Srecko Brlek. Springer Verlag, 2016. p. 102-113 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9840).

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

TY - GEN

T1 - Outfix-guided insertion

AU - Cho, Da Jung

AU - Han, Yo Sub

AU - Ng, Timothy

AU - Salomaa, Kai

N1 - Funding Information: 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 2015 and the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512). Ng and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2016.

PY - 2016

Y1 - 2016

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 nonregular. 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.

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 nonregular. 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.

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

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

U2 - 10.1007/978-3-662-53132-7_9

DO - 10.1007/978-3-662-53132-7_9

M3 - Conference contribution

AN - SCOPUS:84979295348

SN - 9783662531310

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

SP - 102

EP - 113

BT - Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings

A2 - Reutenauer, Christophe

A2 - Brlek, Srecko

PB - Springer Verlag

T2 - 20th International Conference on Developments in Language Theory, DLT 2016

Y2 - 25 July 2016 through 28 July 2016

ER -

Cho DJ, Han YS, Ng T, Salomaa K. Outfix-guided insertion. In Reutenauer C, Brlek S, editors, Developments in Language Theory - 20th International Conference, DLT 2016, Proceedings. Springer Verlag. 2016. p. 102-113. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-53132-7_9

Outfix-guided insertion

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this