Author name cluster

Timothy Ng

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

Closest substring problems for regular languages

Yo-Sub Han
Sang-Ki Ko
Timothy Ng
Kai Salomaa

The Closest Substring problem asks whether there exists a consensus string w of given length ℓ such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has been studied for finite sets of strings and is known to be NP-hard. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFA) is PSPACE-complete. The problem remains PSPACE-hard even when the input is a deterministic finite automaton and the length ℓ and radius r are given in unary. Also we show that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both NP-hard and coNP-hard.

Details DOI

I&C Journal 2021 Journal Article

Consensus string problem for multiple regular languages

Yo-Sub Han
Sang-Ki Ko
Timothy Ng
Kai Salomaa

The consensus string (or centre string, closest string) of a set S of strings is defined as a string which is within a radius r from all strings in S. We study the consensus string problem for multiple languages recognized by finite automata (FAs). We define the consensus string of languages to be within distance at most r to some string in each of the languages. We also study the decidability and computational complexity of the consensus string problem for multiple formal language instances. We show that the consensus string problem for multiple regular languages is PSPACE -complete even when the radius r is fixed. We prove that the problem can be solved in polynomial time when the number of languages is fixed. Finally, we study that the consensus string problem for the class of input-driven languages and show that the problem is decidable.

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 prefix distance

Timothy Ng
David Rappaport
Kai Salomaa

The prefix distance between strings x and y is the number of symbol occurrences in the strings that do not belong to the longest common prefix of x and y. The suffix and the substring distances are defined analogously in terms of the longest common suffix and longest common substring, respectively, of two strings. We show that the set of strings within prefix distance k from an n state DFA (deterministic finite automaton) language can be recognized by a DFA with ( k + 1 ) ⋅ n − k ( k + 1 ) 2 states and that this number of states is needed in the worst case. Also we give tight bounds for the nondeterministic state complexity of the set of strings within prefix, suffix or substring distance k from a regular language.

Details DOI