BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Shinnosuke Seki

Shinnosuke Seki contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityFormal Languages and Automata TheoryData Structures and AlgorithmsDiscrete Mathematics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2013arXiv

3-color Bounded Patterned Self-assembly

Patterned self-assembly tile set synthesis PATS is the problem of finding a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the NP-completeness of PATS and Seki showed that the PATS problem is already NP-complete for patterns with 60 colors. In search for the minimal number of colors such that PATS remains NP-complete, we introduce multiple bound PATS (mbPATS) where we allow bounds for the numbers of tile types of each color. We show that mbPATS is NP-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the NP-completeness of PATS which is more concise than the previous proofs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Combinatorial Optimization in Pattern Assembly

Pattern self-assembly tile set synthesis (PATS) is a combinatorial optimization problem which aim at minimizing a rectilinear tile assembly system (RTAS) that uniquely self-assembles a given rectangular pattern, and is known to be NP-hard. PATS gets practically meaningful when it is parameterized by a constant c such that any given pattern is guaranteed to contain at most c colors (c-PATS). We first investigate simple patterns and properties of minimum RTASs for them. Then based on them, we design a 59-colored pattern to which 3SAT is reduced, and prove that 59-PATS is NP-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent One-Way and Two-Way Deterministic Automata

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 descriptional complexity point of view. We prove that for each one-way nondeterministic automaton with $n$ states there exist Parikh equivalent one-way and two-way deterministic automata with $e^{O(\sqrt{n \ln n})}$ and $p(n)$ states, respectively, where $p(n)$ is a polynomial. Furthermore, these costs are tight. In contrast, if all the words accepted by the given automaton contain at least two different letters, then a Parikh equivalent one-way deterministic automaton with a polynomial number of states can be found. Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with h variables there exist Parikh equivalent one-way and two-way deterministic automata with $2^{O(h^2)}$ and $2^{O(h)}$ states, respectively. Even these bounds are tight.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the behavior of tile assembly system at high temperatures

Behaviors of Winfree's tile assembly systems (TASs) at high temperatures are investigated in combination with integer programming of a specific form called threshold programming. First, we propose a way to build bridges from the Boolean satisfiability problem (SAT) to threshold programming, and further to TAS's behavior, in order to prove the NP-hardness of optimizing temperatures of TASs that behave in a way given as input. These bridges will take us further to two important results on the behavior of TASs at high temperatures. The first says that arbitrarily high temperatures are required to assemble some shape by a TAS of "reasonable" size. The second is that for any temperature at least 4 given as a parameter, it is NP-hard to find the minimum size TAS that self-assembles a given shape and works at the given temperature or below.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Iterated Hairpin Completions of Non-crossing Words

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 precisely a singleton language) is always a context-sensitive language and for some words it is known to be non-context-free. However, it is unknown whether regularity of iterated hairpin completion of a given word is decidable. Also the question whether iterated hairpin completion of a word can be context-free but not regular was asked in literature. In this paper we investigate iterated hairpin completions of non-crossing words and, within this setting, we are able to answer both questions. For non-crossing words we prove that the regularity of iterated hairpin completions is decidable and that if iterated hairpin completion of a non-crossing word is not regular, then it is not context-free either.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the regularity of iterated hairpin completion of a single word

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand $w = xαy \calpha$, and outputs $w' = x αy \barα \bar{x}$, where $\bar{x}$ denotes the Watson-Crick complement of $x$. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words $α$ and $\calpha$ that initiate hairpin completion and how they are scattered, we classify the set of all words $w$. For some basic classes of words $w$ containing small numbers of occurrences of $α$ and $\calpha$, we prove that the iterated hairpin completion of $w$ is regular. For other classes with higher numbers of occurrences of $α$ and $\calpha$, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Properties of Pseudo-Primitive Words and their Applications

A pseudo-primitive word with respect to an antimorphic involution θis a word which cannot be written as a catenation of occurrences of a strictly shorter word t and θ(t). Properties of pseudo-primitive words are investigated in this paper. These properties link pseudo-primitive words with essential notions in combinatorics on words such as primitive words, (pseudo)-palindromes, and (pseudo)-commutativity. Their applications include an improved solution to the extended Lyndon-Schützenberger equation u_1 u_2 ... u_l = v_1 ... v_n w_1 ... w_m, where u_1, ..., u_l \in {u, θ(u)}, v_1, ..., v_n \in {v, θ(v)}, and w_1, ..., w_m \in {w, \theata(w)} for some words u, v, w, integers l, n, m \ge 2, and an antimorphic involution θ. We prove that for l \ge 4, n,m \ge 3, this equation implies that u, v, w can be expressed in terms of a common word t and its image θ(t). Moreover, several cases of this equation where l = 3 are examined.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Power of Nondeterminism in Self-Assembly

We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), which was conceived to model artificial molecular self-assembling systems constructed from DNA. Of particular practical importance is to find tile systems that minimize resources such as the number of distinct tile types, each of which corresponds to a set of DNA strands that must be custom-synthesized in actual molecular implementations of the aTAM. We seek to identify to what extent the use of nondeterminism in tile systems affects the resources required by such molecular shape-building algorithms. We first show a "molecular computability theoretic" result: there is an infinite shape S that is uniquely assembled by a tile system but not by any deterministic tile system. We then show an analogous phenomenon in the finitary "molecular complexity theoretic" case: there is a finite shape S that is uniquely assembled by a tile system with c tile types, but every deterministic tile system that uniquely assembles S has more than c tile types. In fact we extend the technique to derive a stronger (classical complexity theoretic) result, showing that the problem of finding the minimum number of tile types that uniquely assemble a given finite shape is Sigma-P-2-complete. In contrast, the problem of finding the minimum number of deterministic tile types that uniquely assemble a shape was shown to be NP-complete by Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanés, and Rothemund (Combinatorial Optimization Problems in Self-Assembly, STOC 2002). The conclusion is that nondeterminism confers extra power to assemble a shape from a small tile system, but unless the polynomial hierarchy collapses, it is computationally more difficult to exploit this power by finding the size of the smallest tile system, compared to finding the size of the smallest deterministic tile system.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Triangular Self-Assembly

We discuss the self-assembly system of triangular tiles instead of square tiles, in particular right triangular tiles and equilateral triangular tiles. We show that the triangular tile assembly system, either deterministic or non-deterministic, has the same power to the square tile assembly system in computation, which is Turing universal. By providing counter-examples, we show that the triangular tile assembly system and the square tile assembly system are not comparable in general. More precisely, there exists square tile assembly system S such that no triangular tile assembly system is a division of S and produces the same shape; there exists triangular tile assembly system T such that no square tile assembly system produces the same compatible shape with border glues. We also discuss the assembly of triangles by triangular tiles and obtain results similar to the assembly of squares, that is to assemble a triangular of size O(N^2), the minimal number of tiles required is in O(log N/log log N).

0 citations0 reviewsNo code linkedOpen access