Outfix-guided insertion

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish
Title of host publicationDevelopments in Language Theory - 20th International Conference, DLT 2016, Proceedings
EditorsChristophe Reutenauer, Srecko Brlek
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783662531310
Publication statusPublished - 2016
Event20th International Conference on Developments in Language Theory, DLT 2016 - Montreal, Canada
Duration: 2016 Jul 252016 Jul 28

Publication series

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


Other20th International Conference on Developments in Language Theory, DLT 2016

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)


Dive into the research topics of 'Outfix-guided insertion'. Together they form a unique fingerprint.

Cite this