20 citations · 30 across the 20 of their papers we have counts for
6 papers · 1 filter
Bandwidth of Nondeterministic Finite Automata
Da-Jung Cho, Szilárd Zsolt Fazekas, Daihei Ise +3
Co-transcriptional splicing generates RNA sequences from a DNA template by deleting subsequences nondeterministically. Recent work showed how to encode an NFA into such a template,…
The Complexity of Fixed-Height Patterned Tile Self-Assembly
Shinnosuke Seki, Andrew Winslow
We characterize the complexity of the PATS problem for patterns of fixed height and color count in variants of the model where seed glues are either chosen or fixed and identical (…
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent One-Way and Two-Way Deterministic Automata
Giovanna J. Lavado, Giovanni Pighizzini, Shinnosuke Seki
We investigate the conversion of one-way nondeterministic finite automata and context-free grammars into Parikh equivalent one-way and two-way deterministic finite automata, from a…
Iterated Hairpin Completions of Non-crossing Words
Lila Kari, Steffen Kopecki, Shinnosuke Seki
Iterated hairpin completion is an operation on formal languages that is inspired by the hairpin formation in DNA biochemistry. Iterated hairpin completion of a word (or more precis…
Absoluteness of subword inequality is undecidable
Shinnosuke Seki
Mateescu, Salomaa, and Yu asked: is it decidable whether a given subword history assumes only non-negative values for all words over a given alphabet. In this paper, we solve this…
On the regularity of iterated hairpin completion of a single word
Lila Kari, Steffen Kopecki, Shinnosuke Seki
Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand $w = xαy \calpha$, and outputs , where $\bar{…