Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875829 | Theoretical Computer Science | 2017 | 15 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Da-Jung Cho, Yo-Sub Han, Timothy Ng, Kai Salomaa,