20 citations · 30 across the 20 of their papers we have counts for
21 papers
A Congestion Parameter for Depth-First Graph Traversals
Codaline Bourotte, Gwendal Ducloz, Pekka Orponen +1
We explore a new graph parameter, the KLX number, which quantifies the minimum edge congestion of depth-first search (DFS) traversals of a given graph. Originally motivated by a pr…
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,…
A general architecture of oritatami systems for simulating arbitrary finite automata
Yo-Sub Han, Hwee Kim, Yusei Masuda +1
In this paper, we propose an architecture of oritatami systems with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami s…
Know When to Fold 'Em: Self-Assembly of Shapes by Folding in Oritatami
Erik D. Demaine, Jacob Hendricks, Meagan Olsen +5
An oritatami system (OS) is a theoretical model of self-assembly via co-transcriptional folding. It consists of a growing chain of beads which can form bonds with each other as the…
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 (…
A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tile set synthesis
Aleck Johnsen, Ming-Yang Kao, Shinnosuke Seki
Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular (color) pattern. For k >= 1, k-PATS is a variant…