Author name cluster

Da-Jung Cho

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

TCS Journal 2019 Journal Article

Bound-decreasing duplication system

Da-Jung Cho
Yo-Sub Han
Hwee Kim

We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates strings from an initial string using the bound-decreasing duplication operation. We show that there exists a nondeterministic finite-state automaton (NFA) accepting all strings generated by the bound-decreasing duplication system when an initial input is a single string; in other words, the bound-decreasing duplication system produces a regular language. This helps us to calculate the system capacity based on the corresponding NFA. Furthermore, we revisit a deduplication operation—a reverse process of duplication—on an NFA that transforms a given NFA to a smaller NFA while generating the same language by the string duplication system.

Details DOI

TCS Journal 2019 Journal Article

Site-directed insertion: Language equations and decision problems

Da-Jung Cho
Yo-Sub Han
Kai Salomaa
Taylor J. Smith

Site-directed insertion is an overlapping insertion operation that can be viewed as analogous to the overlap assembly or chop operations that concatenate strings by overlapping a suffix and a prefix of the argument strings. We consider decision problems and language equations involving site-directed insertion. By relying on the tools provided by semantic shuffle on trajectories (M. Domaratzki, Developments in Language Theory 2004) we show that one variable equations involving site-directed insertion and regular constants can be solved algorithmically. We consider also maximal and minimal variants of the site-directed insertion operation and the nondeterministic state complexity of site-directed insertion.

Details DOI

TCS Journal 2017 Journal Article

Outfix-guided insertion

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

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.

Details DOI

TCS Journal 2017 Journal Article

Pseudoknot-generating operation

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

A pseudoknot is a crucial intra-molecular structure formed primarily in RNA strands and closely related to important biological processes. This motivates us to define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation. We design an efficient algorithm that decides whether or not a given string is a pseudoknot of a regular language L. Our algorithm runs in linear time if L is given by a deterministic finite automaton. We study closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms that check whether or not a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable.

Details DOI

TCS Journal 2017 Journal Article

State complexity of permutation on finite languages over a binary alphabet

Da-Jung Cho
Daniel Goč
Yo-Sub Han
Sang-Ki Ko
Alexandros Palioudakis
Kai Salomaa

The set of all strings Parikh equivalent to a string in a language L is called the permutation of L. The permutation of a finite n-state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with n 2 − n + 2 2 states. We show that if the language consists of equal length binary strings the bound can be improved to f ( n ) = n 2 + n + 1 3 and for every n congruent to 1 modulo 3 there exists an n-state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L ( A ) needs f ( n ) states.

Details DOI

TCS Journal 2016 Journal Article

State complexity of inversion operations

Da-Jung Cho
Yo-Sub Han
Sang-Ki Ko
Kai Salomaa

The reversal operation is well-studied in the literature and the deterministic (respectively, nondeterministic) state complexity of reversal is known to be 2 n (respectively, n). We consider the inversion operation where some substring of the given string is reversed. Formally, the inversion (respectively, prefix-inversion) of a language L consists of all strings u x R v such that u x v ∈ L (respectively, all strings u R x where u x ∈ L ). We show that the nondeterministic state complexity of prefix-inversion is Θ ( n 2 ) and that of inversion is Θ ( n 3 ). We show that the deterministic state complexity of prefix-inversion is at most 2 n ⋅ log ⁡ n + n and has lower bound 2 Ω ( n log ⁡ n ). The same lower bound holds for the state complexity of inversion, but for inversion we do not have a matching upper bound. We also study the state complexity of other variants of the inversion operation.

Details DOI

TCS Journal 2015 Journal Article

Alignment with non-overlapping inversions and translocations on two strings

Da-Jung Cho
Yo-Sub Han
Hwee Kim

An inversion and a translocation are important in bio sequence analysis and motivate researchers to consider the sequence alignment problem using these operations. Based on inversion and translocation, we introduce a new alignment problem with non-overlapping inversions and translocations—given two strings x and y, find an alignment with non-overlapping inversions and translocations for x and y. This problem has interesting application for finding a common sequence from two mutated sequences. We, in particular, consider the alignment problem when non-overlapping inversions and translocations are allowed for both x and y. We design an efficient algorithm that determines the existence of such an alignment and retrieves an alignment, if exists.

Details DOI

TCS Journal 2014 Journal Article

Decidability of involution hypercodes

Da-Jung Cho
Yo-Sub Han
Sang-Ki Ko

Given a finite set X of strings, X is a hypercode if a string in X is not a subsequence of any other string in X. We consider hypercodes for involution codes, which are useful for DNA strand design, and define an involution hypercode. We then tackle the involution hypercode decidability problem; that is, to determine whether or not a given language is an involution hypercode. Based on the hypercode properties, we design a polynomial runtime algorithm for regular languages. We also prove that it is decidable whether or not a context-free language is an involution hypercode. Note that it is undecidable for some other involution codes such as involution prefix codes, suffix codes, and k-intercodes.

Details DOI