Author name cluster

Hwee Kim

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.

5 papers

1 author row

TCS Journal 2021 Journal Article

A general architecture of oritatami systems for simulating arbitrary finite automata

Yo-Sub Han
Hwee Kim
Yusei Masuda
Shinnosuke Seki

In this paper, we propose an architecture of oritatami systems, a mathematical model of RNA cotranscriptional folding, with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known to be Turing-universal but the simulation available so far requires 542 bead types and O ( t 4 log 2 ⁡ t ) steps in order to simulate t steps of a Turing machine. The architecture we propose employs only 337 bead types and requires just O ( t | Q | 4 | Σ | 2 ) steps to simulate an NFA with a state set Q working on a word of length t over an alphabet Σ.

Details DOI

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

Ruleset optimization on isomorphic oritatami systems

Yo-Sub Han
Hwee Kim

We study an optimization problem of a computational folding model, proving its hardness and proposing heuristic algorithms. RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized out of a gene. An oritatami model (OM) is a computational model of this phenomenon that lets its sequence of beads (abstract molecules) fold cotranscriptionally by the interactions between beads, according to its ruleset. We study the problem of reducing the ruleset size, while keeping the terminal conformations geometrically the same. We first prove the hardness of finding the smallest ruleset, and then suggest two approaches that reduce the ruleset size efficiently.

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 2015 Journal Article

Non-overlapping inversion on strings and languages

Hwee Kim
Yo-Sub Han

Given a string, a non-overlapping inversion is to reverse some non-overlapping fragments of the string simultaneously. We define a non-overlapping inversion operation to be the computation of all possible non-overlapping inversions. We apply the operation on a string, which gives rise to a set of strings, and construct an NFA recognizing the set. Then, we design an efficient DFA reduction algorithm from the resulting NFA. We also consider the non-overlapping inversion operation on a language and show the closure properties for regular, context-free and context-sensitive languages. We furthermore examine iterative non-overlapping inversions and establish the closure properties. Finally, we introduce non-overlapping inversion-free languages and present the decidability results for regular and context-free languages.

Details DOI