Timothy Ng 0001

dblp:157/6118-1 · DBLP profile ↗
← Back
17ranked-venue papers
5as first author
3since 2021 · last 2021
0000-0001-9980-6976ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 15 · 5 first-author · 2 since 2021Artificial intelligence and machine learning · 1 · 1 since 2021Applied, interdisciplinary, general and emerging computing · 1
YearPublicationVenuePosition
2021 Consensus string problem for multiple regular languages
Yo-Sub Han, Sang-Ki Ko, Timothy Ng 0001, Kai Salomaa
Inf. Comput.3
2021 Conjugate word blending: formal model and experimental implementation by XPCR
Francesco Bellamoli, Giuditta Franco, Lila Kari, Silvia Lampis, Timothy Ng 0001
Nat. Comput.5
2021 Closest substring problems for regular languages
Yo-Sub Han, Sang-Ki Ko, Timothy Ng 0001, Kai Salomaa
Theor. Comput. Sci.3
2020 Descriptional Complexity of Semi-simple Splicing Systems
Lila Kari, Timothy Ng 0001
DLT2
2020 Word Blending in Formal Languages
abstract
In this paper we define and investigate a binary word operation that formalizes an experimentally observed outcome of DNA computations, performed to generate a small gene library, and implemented using a DNA recombination technique called Cross-pairing Polymerase Chain Reaction (XPCR). The word ble nding between two words αwγ1 and γ2wβ that share a non-empty overlap w, results in αwβ. Interestingly, this phenomenon has been observed independently in linguistics, under the name “blend word” or “portmanteau”, and is responsible for the creation of words in the English language such as smog (smoke + fog), labradoodle (labrador + poodle), and Brangelina (Brad + Angelina). Technically, word blending is related to the binary word operation Latin product, the crossover operation, and simple splicing. We study closure properties of the families in the Chomsky hierarchy under word blending, language equations involving this operation, and its descriptional state complexity when applied to regular languages. We also define iterated word blending and show that, for a given alphabet, there are finitely many languages that can be obtained from an initial language by iterated word blending.
Srujan Kumar Enaganti, Lila Kari, Timothy Ng 0001
Fundam. Informaticae3
2019 State Complexity of Pseudocatenation
Lila Kari, Timothy Ng 0001
LATA2
2018 Closest Substring Problems for Regular Languages
Yo-Sub Han, Sang-Ki Ko, Timothy Ng 0001, Kai Salomaa
DLT3
2017 Relative Prefix Distance Between Languages
Timothy Ng 0001, David Rappaport, Kai Salomaa
DLT1
2017 Consensus String Problem for Multiple Regular Languages
Yo-Sub Han, Sang-Ki Ko, Timothy Ng 0001, Kai Salomaa
LATA3
2017 Pseudoknot-generating operation
Da-Jung Cho, Yo-Sub Han, Timothy Ng 0001, Kai Salomaa
Theor. Comput. Sci.3
2017 Outfix-guided insertion
Da-Jung Cho, Yo-Sub Han, Timothy Ng 0001, Kai Salomaa
Theor. Comput. Sci.3
2017 State complexity of prefix distance
Timothy Ng 0001, David Rappaport, Kai Salomaa
Theor. Comput. Sci.1
2016 Outfix-Guided Insertion - (Extended Abstract)
Da-Jung Cho, Yo-Sub Han, Timothy Ng 0001, Kai Salomaa
DLT3
2016 Pseudoknot-Generating Operation
Da-Jung Cho, Yo-Sub Han, Timothy Ng 0001, Kai Salomaa
SOFSEM3
2016 Prefix Distance Between Regular Languages
Timothy Ng 0001
CIAA1
2015 State Complexity of Neighbourhoods and Approximate Pattern Matching
Timothy Ng 0001, David Rappaport, Kai Salomaa
DLT1
2015 State Complexity of Prefix Distance
Timothy Ng 0001, David Rappaport, Kai Salomaa
CIAA1