関 新之助
| 情報・ネットワーク工学専攻 | 准教授 |
| Ⅰ類（情報系） | 准教授 |
研究者情報
経歴
- 2018年09月 - 現在
Ecole Normale Superieure de Lyon, Invited Professor, フランス共和国 - 2013年09月 - 2015年03月
Academy of Finland, Postdoctoral Researcher, Principal Investigator, フィンランド共和国 - 2012年02月 - 2013年08月
Aalto University, Department of Information and Computer Science, Postdoctoral Researcher, フィンランド共和国 - 2011年05月01日 - 2012年02月15日
京都大学, 薬学研究科, 博士研究員 - 2010年09月 - 2011年04月
University of Western Ontario, Department of Computer Science, Postdoctoral Researcher, カナダ
学歴
委員歴
- 2024年02月 - 現在
Member, Program Committee of the IEEE 3rd Conference on Information Technology and Data Science (CITDS 2024) - 2023年11月 - 現在
Member, Program Committee of the 26th International Conference on Descriptional Complexity of Formal Systems (DCFS 2024), 学協会 - 2023年09月 - 現在
Co-chair, Program Committee of the 30th International Conference on DNA Computing and Molecular Programming (DNA30), 学協会 - 2023年08月 - 現在
Member, Organizing Committee of the 28th International Conference on Implementation and Application of Automata (CIAA 2024), 学協会 - 2023年07月 - 現在
Member, Organizing Committee of the 21st International Conference on Unconventional Computation and Natural Computation (UCNC 2024), 学協会 - 2022年09月 - 現在
Member, Steering Committee of the International Conference on Machines, Computations, and Universality (MCU), 学協会 - 2021年10月 - 現在
Co-chair, Steering Committee of the International Conference on Unconventional Computation and Natural Computation (UCNC), Co-chair - 2019年09月 - 現在
Area Editor, New Generation Computing, Editorial Board, 学協会 - 2018年04月 - 現在
Advisory Board, Springer Natural Computing Book-Series, 学協会 - 2017年08月 - 現在
Member, Steering Committee of International Conference on Developments in Language Theory (DLT), 学協会 - 2022年09月 - 2023年09月
Member, Program Committee of the 29th International Conference on DNA Computing and Molecular Programming (DNA29), 学協会 - 2022年09月 - 2023年09月
Member, Program Committee of the 27th International Conference on Implementation and Application of Automata (CIAA2023), 学協会 - 2022年07月 - 2023年07月
Member, Program Committee of the 25th International Conference on Descriptional Complexity of Formal Systems (DCFS 2023), 学協会 - 2022年04月 - 2023年07月
Member, Program Committee of the 19th Conference on Computability in Europe (CiE2023), 学協会 - 2018年04月01日
専門委員, 情報処理学会アルゴリズム研究会 - 2018年04月01日
関 新之助, 情報処理学会アルゴリズム研究会 - 2014年10月01日
関 新之助, 情報処理学会論文誌「数理モデル化と応用」編集委員会, 学協会
研究活動情報
受賞
論文
- Towards composable computations by RNA co-transcriptional folding: A proof-of-concept demonstration of nested loops in oritatami
Szilárd Zsolt Fazekas; Naoya Iwano; Yu Kihara; Ryuichi Matsuoka; Shinnosuke Seki; Hinano Takeuchi
責任著者, Theoretical Computer Science, Elsevier BV, 999巻, 掲載ページ 114550-114550, 出版日 2024年06月, 査読付, 招待
研究論文（学術雑誌）, 英語 - Freezing 1-tag systems with states
Szilard Zsolt Fazekas; Shinnosuke Seki
責任著者, Electronic Proceedings in Theoretical Computer Science (EPTCS), Proceedings of the 16th International Conference on Automata and Formal Languages (AFL 2023), 386号, 掲載ページ 82-95, 出版日 2023年09月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Ok: A kinetic model for locally reconfigurable molecular systems
Pierre Marcus; Nicolas Schabanel; Shinnosuke Seki
責任著者, Visions of DNA Nanotechnology at 40 for the Next 40, 掲載ページ 229-240, 出版日 2023年05月, 査読付, 招待
研究論文（学術雑誌）, 英語 - Oritatami systems assemble shapes no less complex than tile assembly model (aTAM)
Daria Pchelina; Nicolas Schabanel; Shinnosuke Seki; Guillaume Theyssier
Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), LIPIcs 219巻, 掲載ページ 51:1-51:23, 出版日 2022年03月09日, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Square network on a word
Szilard Zsolt Fazekas; Shinnosuke Seki
Theoretical Computer Science, Elsevier, 894巻, 26号, 掲載ページ 121-134, 出版日 2021年11月, 査読付, Left-aligned last occurrences of squares (double-square) have provided profound insights into the question of how many distinct squares can be packed on a word ω of length n and brought the best known upper bound 11n/6. Other types of alignments such as being center-aligned as well as long distance relations such as being the occurrences of the same square incorporate the squares on ω into a bipartite graph of the squares and positions {1,2,…,n}, which we call the square network. Packing more and more squares in a limited space certainly induces specific kinds of subgraphs once the square density exceeds a threshold, and if one of the subgraphs is known to be forbidden, the threshold provides an upper bound on the number of distinct squares. In this paper, we designate a specific position of double-squares as P1 and obtain certain induced subgraphs as well as forbidden ones guaranteed by the presence of P1-aligned double squares; an induced subgraph of particular interest expresses the global uniqueness of squares involved.
研究論文（学術雑誌）, 英語 - Simple intrinsic simulation of cellular automata in oritatami molecular folding model
Daria Pchelina; Nicolas Schabanel; Shinnosuke Seki; Yuki Ubukata
Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN 2020), Springer, LNCS 12118巻, 掲載ページ 425-436, 出版日 2021年01月05日, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Linear bounds on the size of the conformations in greedy deterministic oritatami
Szilard Zsolt Fazekas; Hwee Kim; Ryuichi Matsuoka; Reoto Morita; Shinnosuke Seki
International Journal of Foundations of Computer Science, World Scientific Publishing Company, 32巻, 5号, 掲載ページ 575-596, 出版日 2021年, 査読付
研究論文（学術雑誌）, 英語 - A general architecture of oritatami systems for simulating arbitrary finite automata
Yo-Sub Han; Hwee Kim; Yusei Masuda; Shinnosuke Seki
Theoretical Computer Science, Springer, 870巻, 16号, 掲載ページ 29-52, 出版日 2021年, 査読付
研究論文（学術雑誌）, 英語 - Counting infinitely by oritatami co-transcriptional folding
Kohei Maruyama; Shinnosuke Seki
Natural Computing, Springer, 20巻, 2号, 掲載ページ 329-340, 出版日 2021年, 査読付
研究論文（学術雑誌）, 英語 - Transcript design problem of oritatami systems
Yo-Sub Han; Hwee Kim; Shinnosuke Seki
Natural Computing, Springer, 19巻, 2号, 掲載ページ 323-335, 出版日 2020年, 査読付
研究論文（学術雑誌）, 英語 - Self-attraction removal from oritatami systems
Yo-Sub Han; Hwee Kim; Trent A. Rogers; Shinnosuke Seki
International Journal of Foundations of Computer Science, 30巻, 6-7号, 掲載ページ 1047-1067, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - On the Power of Oritatami Cotranscriptional Folding with Unary Bead Sequence.
Szilárd Zsolt Fazekas; Kohei Maruyama; Reoto Morita; Shinnosuke Seki
Proceedings of the 15th International Conference on Theory and Applications of Models of Computation (TAMC 2019), Springer, LNCS 11436巻, 掲載ページ 188-207, 出版日 2019年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Oritatami: a computational model for molecular co-transcriptional folding
Cody Geary; Pierre-Etienne Meunier; Nicolas Schabanel; Shinnosuke Seki
International Journal of Molecular Sciences, MDPI, 20巻, 9号, 掲載ページ 2259, 出版日 2019年, 査読付
研究論文（学術雑誌）, 英語 - Single-stranded architectures for computing
Shinnosuke Seki
Proceedings of the 23rd International Conference on Developments in Language Theory (DLT 2019), Springer, LNCS 11647巻, 掲載ページ 41-56, 出版日 2019年, 査読付, 招待
研究論文（国際会議プロシーディングス）, 英語 - Nondeterministic seedless oritatami systems and hardness of testing their equivalence
Yo-Sub Han; Hwee Kim; Makoto Ota; Shinnosuke Seki
Natural Computing, Springer, 17巻, 1号, 掲載ページ 67-79, 出版日 2018年, 査読付
研究論文（学術雑誌）, 英語 - Towards the algorithmic molecular self-assembly of fractals by cotranscriptional folding
Yusei Masuda; Shinnosuke Seki; Yuki Ubukata
Proceedings of the 23rd International Conference on Implementation and Applications of Automata (CIAA2018), Springer, LNCS巻, 10977号, 掲載ページ 261-273, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Know when to fold 'em: Self-assembly of shapes by folding in oritatami
Erik Demaine; Jacob Hendricks; Meagan Olsen; Matthew J. Patitz; Trent A. Rogers; Nicolas Schabanel; Shinnosuke Seki; Hadley Thoams
Proceedings of the 24th International Conference on DNA Computing and Molecular Programming (DNA 24), Springer, LNCS巻, 11145号, 掲載ページ 19-36, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Transcript design problem of oritatami systems
Yo-Sub Han; Hwee Kim; Shinnosuke Seki
Proceedings of the 24th International Conference on DNA Computing and Molecular Programming (DNA 24), Springer, LNCS巻, 11145号, 掲載ページ 139-154, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Proving the Turing universality of oritatami co-transcriptional folding
Cody Geary; Pierre-Etienne Meunier; Nicolas Schabanel; Shinnosuke Seki
Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC2018), Schloss Dagstuhl, LIPIcs 123巻, 掲載ページ 23:1-23:13, 出版日 2018年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - The Complexity of Fixed-Height Patterned Tile Self-Assembly
Shinnosuke Seki; Andrew Winslow
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, WORLD SCIENTIFIC PUBL CO PTE LTD, 28巻, 5号, 掲載ページ 465-482, 出版日 2017年08月, 査読付, 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 (so-called non-uniform and uniform variants). We prove that both variants are NP-complete for patterns of height 2 or more and admit O(n)-time algorithms for patterns of height 1. We also prove that if the height and number of colors in the pattern is fixed, the non-uniform variant admits a O(n)-time algorithm while the uniform variant remains NP-complete. The NP-completeness results use a new reduction from a constrained version of a problem on finite state transducers.
研究論文（学術雑誌）, 英語 - Self-attraction removal from oritatami systems
Yo-Sub Han; Hwee Kim; Trent A. Rogers; Shinnosuke Seki
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10316巻, 掲載ページ 164-176, 出版日 2017年, 査読付, RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.
研究論文（国際会議プロシーディングス）, 英語 - Oritatami System; a Survey and the Impossibility of Simple Simulation at Small Delays
Trent A. Rogers; Shinnosuke Seki
FUNDAMENTA INFORMATICAE, IOS PRESS, 154巻, 1-4号, 掲載ページ 359-372, 出版日 2017年, 査読付, RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research topics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay delta that cannot be simulated by any oritatami system at larger delay.
研究論文（学術雑誌）, 英語 - Self-attraction removal from oritatami systems
Yo-Sub Han; Hwee Kim; Trent A. Rogers; Shinnosuke Seki
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10316巻, 掲載ページ 164-176, 出版日 2017年, 査読付, RNA cotranscriptional folding refers to the phenomenon in which an RNA transcript folds upon itself while being synthesized (transcribed). Oritatami is a computational model of this phenomenon, which lets its transcript, a sequence of beads (abstract molecules) fold cotranscriptionally via interactions between beads according to its ruleset. In this paper, we study the problem of removing self-attractions, which lets a bead interact with another bead of the same kind, from a given oritatami system without changing its behavior. We provide an algorithm for that with overhead linear in the delay parameter, which should be considerably smaller than the length of its transcript. We also show that this overhead is tight.
研究論文（国際会議プロシーディングス）, 英語 - The extended equation of Lyndon and Schutzenberger
Florin Manea; Mike Muller; Dirk Nowotka; Shinnosuke Seki
Journal of Computer and System Sciences, Elsevier, 85巻, 掲載ページ 132-167, 出版日 2016年11月26日, 査読付
研究論文（学術雑誌）, 英語 - Rule set design problems for oritatami system
Makoto Ota; Shinnosuke Seki
Theoretical Computer Science, Elsevier, 671巻, 掲載ページ 26-35, 出版日 2016年09月22日, 査読付
研究論文（学術雑誌）, 英語 - Programming biomolecules that fold greedily during transcription
Cody Geary; Pierre-Etienne Meunier; Nicolas Schabanel; Shinnosuke Seki
MFCS 2016: 41st International Symposium on Mathematical Foundations of Computer Science, LIPIcs 58巻, 掲載ページ 43:1-43:14, 出版日 2016年08月22日, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Binary pattern tile set synthesis is NP-hard
Lila Kari; Steffen Kopecki; Pierre-Etienne Meunier; Matthew J. Patitz; Shinnosuke Seki
Algorithmica, Springer, 78巻, 1号, 掲載ページ 1-46, 出版日 2016年04月26日, 査読付
研究論文（学術雑誌）, 英語 - The Complexity of Fixed-Height Patterned Tile Self-assembly
Shinnosuke Seki; Andrew Winslow
Implementation and Application of Automata, SPRINGER INT PUBLISHING AG, 9705巻, LNCS 9705号, 掲載ページ 248-259, 出版日 2016年, 査読付, We characterize the complexity of the PATSproblem for patterns of fixed height and color count in variants of the model where seed glues are either chosen or fixed and identical (so-called non-uniform and uniform variants). We prove that both variants are NP-complete for patterns of height 2 or more and admit O(n)-time algorithms for patterns of height 1. We also prove that if the height and number of colors in the pattern is fixed, the non-uniform variant admits a O(n)-time algorithm while the uniform variant remains NP-complete. The NP-completeness results use a new reduction from a constrained version of a problem on finite state transducers.
研究論文（国際会議プロシーディングス）, 英語 - Nondeterministic seedless oritatami systems and hardness of testing their equivalence
Yo-Sub Han; Hwee Kim; Makoto Ota; Shinnosuke Seki
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 9818巻, 掲載ページ 19-34, 出版日 2016年, 査読付, The oritatami system (OS) is a model of computation by cotranscriptional folding, being inspired by the recent experimental succeess of RNA origami to self-assemble an RNA tile cotranscriptionally.The OSs implemented so far, including binary counter and Turing machine simulator, are deterministic, that is, uniquely fold into one conformation, while nondeterminism is intrinsic in biomolecular folding.We introduce nondeterminism to OS (NOS) and propose an NOS that chooses an assignment of Boolean values nondeterministically and evaluates a logical formula on the assignment.This NOS is seedless in the sense that it does not require any initial conformation to begin with like the RNA origami.The NOS allows to prove the co-NP hardness of deciding, given two NOSs, if there exists no conformation that one of them folds into but the other does not.
研究論文（国際会議プロシーディングス）, 英語 - A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
Aleck Johnsen; Ming-Yang Kao; Shinnosuke Seki
Journal of Combinatorial Optimization, Springer, 33巻, 2号, 掲載ページ 496-529, 出版日 2015年11月24日, 査読付
研究論文（学術雑誌）, 英語 - Program Size and Temperature in Self-Assembly
Ho-Lin Chen; David Doty; Shinnosuke Seki
ALGORITHMICA, SPRINGER, 72巻, 3号, 掲載ページ 884-899, 出版日 2015年07月, 査読付, Winfree's abstract Tile Assembly Model is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing "seed" assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman et al. (Combinatorial optimization problems in self-assembly, STOC 2002). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its "temperature" (the binding strength threshold required for a tile to attach).
研究論文（学術雑誌）, 英語 - Dynamic Simulation of 1D Cellular Automata in the Active aTAM
Natasa Jonoska; Daria Karpenko; Shinnosuke Seki
NEW GENERATION COMPUTING, SPRINGER, 33巻, 3号, 掲載ページ 271-295, 出版日 2015年07月, 査読付, The Active aTAM is a tile based model for self-assembly where tiles are able to transfer signals and change identities according to the signals received. We extend Active aTAM to include deactivation signals and thereby allow detachment of tiles. We show that the model allows a dynamic simulation of cellular automata with assemblies that do not record the entire computational history but only the current updates of the states, and thus provide a way for (a) algorithmic dynamical structural changes in the assembly and (b) reusable space in self-assembly. The simulation is such that at a given location the sequence of tiles that attach and detach corresponds precisely to the sequence of states the synchronous cellular automaton generates at that location.
研究論文（学術雑誌）, 英語 - 3-color bounded patterned self-assembly
Lila Kari; Steffen Kopecki; Shinnosuke Seki
NATURAL COMPUTING, SPRINGER, 14巻, 2号, 掲載ページ 279-292, 出版日 2015年06月, 査読付, The problem of patterned self-assembly tile set synthesis (PATS) is to find 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.
研究論文（学術雑誌）, 英語 - Square-Density Increasing Mappings
Florin Manea; Shinnosuke Seki
COMBINATORICS ON WORDS, WORDS 2015, SPRINGER-VERLAG BERLIN, 9304巻, 掲載ページ 160-169, 出版日 2015年, 査読付, The square conjecture claims that the number of distinct squares, factors of the form xx, in a word is at most the length of the word. Being associated with it, it is also conjectured that binary words have the largest square density. That is, it is sufficient to solve the square conjecture for words over binary alphabet. We solve this subsidiary conjecture affirmatively, or more strongly, we prove the irrelevance of the alphabet size in solving the square conjecture, as long as the alphabet is not unary. The tools we employ are homomorphisms with which one can convert an arbitrary word into a word with strictly larger square density over an intended alphabet.
研究論文（国際会議プロシーディングス）, 英語 - Semilinear Sets and Counter Machines: a Brief Survey
Oscar H. Ibarra; Shinnosuke Seki
FUNDAMENTA INFORMATICAE, IOS PRESS, 138巻, 1-2号, 掲載ページ 61-76, 出版日 2015年, 査読付, Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh's theorem enables us to represent any semilinear set as a push-down automaton (PDA). We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh's theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words.
研究論文（学術雑誌）, 英語 - Binary Pattern Tile Set Synthesis Is NP-hard
Lila Kari; Steffen Kopecki; Pierre-Etienne Meunier; Matthew J. Patitz; Shinnosuke Seki
Automata, Languages, and Programming, Pt I, SPRINGER-VERLAG BERLIN, 9134巻, 掲載ページ 1022-1034, 出版日 2015年, 査読付, We solve an open problem, stated in 2008, about the feasibility of designing efficient algorithmic self-assembling systems which produce 2-dimensional colored patterns. More precisely, we show that the problem of finding the smallest tile assembly system which will self-assemble an input pattern with 2 colors (i.e., 2-Pats) is NP-hard. One crucial lemma makes use of a computer-assisted proof, which is a relatively novel but increasingly utilized paradigm for deriving proofs for complex mathematical problems. This tool is especially powerful for attacking combinatorial problems, as exemplified by the proof for the four color theorem and the recent important advance on the Erdos discrepancy problem using computer programs. In this paper, these techniques will be brought to a new order of magnitude, computational tasks corresponding to one CPU-year. We massively parallelize our program, and provide a full proof of its correctness. Its source code is freely available online.
研究論文（国際会議プロシーディングス）, 英語 - Transfer matrix analysis of one-dimensional majority cellular automata with thermal noise
Remi Lemoy; Alexander Mozeika; Shinnosuke Seki
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, IOP PUBLISHING LTD, 47巻, 10号, 掲載ページ 105001-105001, 出版日 2014年03月, 査読付, Thermal noise in a cellular automaton (CA) refers to a random perturbation in its function which eventually leads the automaton to an equilibrium state controlled by a temperature parameter. We study the one-dimensional majority-3 CA under this model of noise. Without noise, each cell in the automaton decides its next state by majority voting among itself and its left and right neighbour cells. Transfer matrix analysis shows that the automaton always reaches a state in which every cell is in one of its two states with probability 1/2 and thus cannot remember even one bit of information. Numerical experiments, however, support the possibility of reliable computation for a long but finite time.
研究論文（学術雑誌）, 英語 - A Stronger Square Conjecture on Binary Words
Natasa Jonoska; Florin Manea; Shinnosuke Seki
SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 8327巻, 掲載ページ 339-350, 出版日 2014年, 査読付, We propose a stronger conjecture regarding the number of distinct squares in a binary word. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is upper bounded by the length of the word. Here, we conjecture that in the case of a word of length n over the alphabet {a, b}, the number of distinct squares is upper bounded by 2k-1/2k+2n, where k is the least of the number of a's and the number of b's. We support the conjecture by showing its validity for several classes of binary words. We also prove that the bound is tight.
研究論文（国際会議プロシーディングス）, 英語 - Operational State Complexity under Parikh Equivalence
Giovanna J. Lavado; Giovanni Pighizzini; Shinnosuke Seki
DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2014, SPRINGER-VERLAG BERLIN, 8614巻, 掲載ページ 294-305, 出版日 2014年, 査読付, We investigate, under Parikh equivalence, the state complexity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shuffle, and reversal, we obtain a polynomial state complexity over any fixed alphabet, in contrast to the intrinsic exponential state complexity of some of these operations in the classical version. For projection we prove a superpolynomial state complexity, which is lower than the exponential one of the corresponding classical operation. We also prove that for each two deterministic automata A and B it is possible to obtain a deterministic automaton with a polynomial number of states whose accepted language has as Parikh image the intersection of the Parikh images of the languages accepted by A and B. Finally, we prove that for each finite set there exists a small context-free grammar defining a language with the same Parikh image.
研究論文（国際会議プロシーディングス）, 英語 - Generalised Lyndon-Schutzenberger Equations
Florin Manea; Mike Mueller; Dirk Nowotka; Shinnosuke Seki
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2014, PT I, SPRINGER-VERLAG BERLIN, 8634巻, 掲載ページ 402-+, 出版日 2014年, 査読付, We fully characterise the solutions of the generalised Lyndon-Schutzenberger word equations u(1) ... u(l) = v(1) ... v(m)w(1) ... w(n), where u(i) is an element of {u, theta(u)} for all 1 <= i <= l, v(j) is an element of {v, theta(v)} for all 1 < j <= m, w(k) is an element of {w, theta(w)} for all 1 <= k <= n, and theta is an antimorphic involution. More precisely, we show for which f, m, and n such an equation has only theta-periodic solutions, i.e., u, v, w is an element of {t, theta(t)}* for some word t, closing an open problem by Czeizler et al. (2009).
研究論文（国際会議プロシーディングス）, 英語 - On computational complexity of graph inference from counting
Szilárd Zsolt Fazekas; Hiro Ito; Yasushi Okuno; Shinnosuke Seki; Kei Taneishi
Natural Computing, Springer, 12巻, 4号, 掲載ページ 589-603, 出版日 2013年12月, 査読付, In de novo drug design, chemical compounds are quantitized as real-valued vectors called chemical descriptors, and an optimization algorithm runs on known drug-like chemical compounds in a database and outputs an optimal chemical descriptor. Since structural information is needed for chemical synthesis, we must infer chemical graphs from the obtained descriptor. This is formalized as a graph inference problem from a real-value vector. By generalizing subword history, which was originally introduced in formal language theory to extract numerical information of words and languages based on counting, we propose a comprehensive framework to investigate the computational complexity of chemical graph inference. We also propose a (pseudo-)polynomial-time algorithm for inferring graphs in a class of practical importance from spectrums. © 2012 Springer Science+Business Media Dordrecht.
研究論文（学術雑誌）, 英語 - On the open problem of Ginsburg concerning semilinear sets and related problems
Oscar H. Ibarra; Shinnosuke Seki
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 501巻, 掲載ページ 11-19, 出版日 2013年08月, 査読付, In his 1966 book, "The Mathematical Theory of Context-Free Languages", S. Ginsburg posed the following open problem: Find a decision procedure for determining if an arbitrary semilinear set is a finite union of stratified linear sets. It turns out that this problem (which remains open) is equivalent to the problem of synchronizability of multitape machines. Given an n-tape automaton M of a given type (e.g., nondeterministic pushdown automaton (NPDA), nondeterministic finite automaton (NFA), etc.) with a one-way read-only head per tape and a right end marker on each tape, we say that M is 0-synchronized (or aligned) if for every n-tuple x = (x(1), . . . , x(n)) that is accepted, there is an accepting computation on x such that at any time during the computation, all heads except those that have reached the end marker are on the same position (i.e., aligned). One of our main contributions is to show that Ginsburg's problem is equivalent to deciding for an arbitrary n-tape NFA M accepting L(M) subset of a(1)* x . . . x a(n)* (where n >= 1 and a(1) , . . . , a(n) an are distinct symbols) whether there exists an equivalent 0-synchronized n-tape NPDA M'. Ginsburg's problem is decidable if M' is required to be an NFA, and we will generalize this decidability over bounded inputs. It is known that if the inputs are unrestricted, the problem is undecidable. We also show several other related decidability and undecidability results.
It may appear, as one of the referees suggested in an earlier version of this paper, that our main result can be written in first order logic. We explain why this is not the case in the Introduction. (C) 2013 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - The power of nondeterminism in self-assembly
Nathan Bryans; Ehsan Chiniforooshan; David Doty; Lila Kari; Shinnosuke Seki
Theory of Computing, 9巻, 掲載ページ 1-29, 出版日 2013年, 査読付
研究論文（学術雑誌）, 英語 - On the behavior of tile assembly system at high temperatures
Shinnosuke Seki; Yasushi Okuno
Computability, IOS Press, 2巻, 2号, 掲載ページ 107-124, 出版日 2013年, 査読付, Behavior of Winfree's tile assembly system (TAS) at high temperatures is 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 τ ≥ 4 given as a parameter, it is NP-hard to find the minimum size TAS that self-assembles a given shape at a temperature at most τ.
研究論文（学術雑誌）, 英語 - Convering nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
Giovanna J. Lavado; Giovanni Pighizzini; Shinnosuke Seki
Information and Computation, Elsevier, 228-229巻, 掲載ページ 1-15, 出版日 2013年, 査読付
研究論文（学術雑誌）, 英語 - On the boundedness property of semilinear sets
Oscar H. Ibarra; Shinnosuke Seki
TAMC 2013: Proceedings of the 10th Annual Conference on Theory and Applications of Models of Computation, Springer, LNCS 7876巻, 掲載ページ 156-168, 出版日 2013年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Combinatorial optimization in pattern assembly (extended abstract)
関新之助
UCNC 2013: Proceedings of the Unconventional Computation and Natural Computation - 12th International Conference, Springer, LNCS 7956巻, 掲載ページ 220-231, 出版日 2013年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - 3-Color Bounded Patterned Self-assemblyY
Lila Kari; Steffen Kopecki; Shinnosuke Seki
DNA COMPUTING AND MOLECULAR PROGRAMMING, DNA 2013, SPRINGER-VERLAG BERLIN, 8141巻, 掲載ページ 105-117, 出版日 2013年, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語 - Computing Minimum Tile Sets to Self-Assemble Color Patterns
Aleck C. Johnsen; Ming-Yang Kao; Shinnosuke Seki
ALGORITHMS AND COMPUTATION, SPRINGER-VERLAG BERLIN, 8283巻, 掲載ページ 699-710, 出版日 2013年, 査読付, Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular pattern. For k >= 1, k-PATS is a variant of PATS that restricts input patterns to those with at most k colors. We prove the NP-hardness of 29-PATS, where the best known is that of 60-PATS.
研究論文（国際会議プロシーディングス）, 英語 - One-reversal counter machines and multihead automata: Revisited
Ehsan Chiniforooshan; Mark Daley; Oscar H. Ibarra; Lila Kari; Shinnosuke Seki
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 454巻, 掲載ページ 81-87, 出版日 2012年10月, 査読付, We investigate the power of (1-reversal) counter machines (finite automata with multiple counters, where each counter can "reverse" only once, i.e., once a counter decrements, it can no longer increment) and one-way multihead finite automata (finite automata with multiple one-way input heads) as a language acceptor. They can be non-deterministic as well as augmented with a pushdown stack. First, we prove that adding a pushdown stack properly strengthens the deterministic counter machines. Non-deterministic counter machines with a pushdown stack are then compared with multihead finite automata. The proof of their incomparability involves an interesting technique: an assumption that a language be accepted by a non-deterministic counter machine would bring a contradictory algorithm to decide an undecidable language. Furthermore, we will show that over bounded languages, these two kinds of machines have the same power, and neither non-determinism nor a pushdown stack makes them stronger. (C) 2012 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
Oscar H. Ibarra; Shinnosuke Seki
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, WORLD SCIENTIFIC PUBL CO PTE LTD, 23巻, 6号, 掲載ページ 1291-1305, 出版日 2012年09月, 査読付, A hounded language L subset of x(1)* ... x(k)* (for some k >= 1 and not-necessarily distinct nonempty words x(1), ... , x(k)) is bounded semilinear if the set Q(L) - {(i(1), ..., i(k)) vertical bar x(1)(i1) ... x(k)(ik) is an element of L} is semilinear, We give characterizations of bounded semilinear languages in terms of one-way and two-way deterministic counter machines.
研究論文（学術雑誌）, 英語 - Absoluteness of subword inequality is undecidable
Shinnosuke Seki
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 418巻, 掲載ページ 116-120, 出版日 2012年02月, 査読付, In a given word, one can count the number of occurrences of other words as a scattered subword. These counts can be "added" and/or "multiplied." A subword history gives an instruction of what words to be counted and how these counts to be added and multiplied with other counts or integer constants, and hence, determines its unique value in a given word. Mateescu, Salomaa, and Yu asked: "is it decidable whether the value of a given subword history is non-negative in all words over a given alphabet?" (absoluteness problem). Another important problem is of whether there exists a word in which the value of a given subword history becomes 0 (equality problem). In this paper, we prove the undecidability of the equality problem and show that the equality problem is polynomial-time Karp reducible to the absoluteness problem: thus, the absoluteness problem is also undecidable. This approach solves the open problem actually under stronger conditions than supposed originally. (C) 2011 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - Iterated Hairpin Completions of Non-crossing Words
Lila Kari; Steffen Kopecki; Shinnosuke Seki
SOFSEM 2012: THEORY AND PRACTICE OF COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 7147巻, 掲載ページ 337-+, 出版日 2012年, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語 - Triangular and hexagonal tile self-assembly systems
Lila Kari; Shinnosuke Seki; Zhi Xu
WTCS 2012: Proceedings of the International Workshop on Theoretical Computer Science, Springer, LNCS 7160巻, 掲載ページ 357-375, 出版日 2012年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata
Giovanna J. Lavado; Giovanni Pighizzini; Shinnosuke Seki
DLT 2012: Proceedings of the 16th International Conference on Developments in Language Theory, Springer, LNCS 7410巻, 掲載ページ 284-295, 出版日 2012年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED
Lila Kari; Shinnosuke Seki
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, WORLD SCIENTIFIC PUBL CO PTE LTD, 22巻, 7号, 掲載ページ 1655-1668, 出版日 2011年11月, 査読付, A general framework of parallel insertion and deletion based on p-schemata is proposed. A p-schema is a set of tuples of words. When being used for parallel insertion of a language into a word, an element of p-schema specifies how to split the word into factors between which the language to be inserted. As its inverse operation, parallel deletion based on the p-schema is defined. Several algebraic properties of these operations such as closure properties of language classes under them are proved. The main contribution of this paper is to propose algorithms to solve language equations involving p-schema-based insertions or deletions based on syntactic congruence. These algorithms not only decide whether a given equation has a solution but construct the set of all of its maximal or minimal solutions. The algorithms are extensible so as to solve some multiple-variables equations and inequalities. Related undecidability results are also presented.
研究論文（学術雑誌）, 英語 - An extension of the Lyndon-Schutzenberger result to pseudoperiodic words
Elena Czeizler; Eugen Czeizler; Lila Kari; Shinnosuke Seki
INFORMATION AND COMPUTATION, ACADEMIC PRESS INC ELSEVIER SCIENCE, 209巻, 4号, 掲載ページ 717-730, 出版日 2011年04月, 査読付, One of the particularities of information encoded as DNA strands is that a string u contains basically the same information as its Watson Crick complement, denoted here as theta(u). Thus, any expression consisting of repetitions of u and theta(u) can be considered in some sense periodic. In this paper, we give a generalization of Lyndon and Schutzenberger's classical result about equations of the form u(l) = V(n)W(m) to cases where both sides involve repetitions of words as well as their complements. Our main results show that, for such extended equations, if l >= 5, n, m >= 3, then all three words involved can be expressed in terms of a common word t and its complement theta(t). Moreover, if l >= 5, then n = m = 3 is an optimal bound. These results are established based on a complete characterization of all possible overlaps between two expressions that involve only some word u and its complement theta(u), which is also obtained in this paper. Crown Copyright (C) 2011 Published by Elsevier Inc. All rights reserved.
研究論文（学術雑誌）, 英語 - Block insertion and deletion on trajectories
Bo Cui; Lila Kari; Shinnosuke Seki
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 412巻, 8-10号, 掲載ページ 714-728, 出版日 2011年03月, 査読付, In this paper, we introduce block insertion and deletion on trajectories, which provide us with a new framework to study properties of language operations. With the parallel syntactical constraint provided by trajectories, these operations properly generalize several sequential as well as parallel binary language operations such as catenation, sequential insertion, k-insertion, parallel insertion, quotient, sequential deletion, k-deletion, etc.
We establish some relationships between the new operations and shuffle and deletion on trajectories, and obtain several closure properties of the families of regular and context-free languages under the new operations. Moreover, we obtain several decidability results of three types of language equation problems which involve the new operations. The first one is to answer, given languages L-1, L-2, L-3 and a trajectory set T. whether the result of an operation between L-1 and L-2 on the trajectory set T is equal to L-3. The second one is to answer, for three given languages L-1, L-2, L-3, whether there exists a set of trajectories such that the block insertion or deletion between L-1 and L-2 on this trajectory set is equal to L-3. The third problem is similar to the second one, but the language L-1 is unknown while languages L-2, L-3 as well as a trajectory set T are given. Crown Copyright (C) 2010 Published by Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - PROPERTIES OF PSEUDO-PRIMITIVE WORDS AND THEIR APPLICATIONS
Lila Kari; Benoit Masson; Shinnosuke Seki
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, WORLD SCIENTIFIC PUBL CO PTE LTD, 22巻, 2号, 掲載ページ 447-471, 出版日 2011年02月, 査読付, A pseudo-primitive word with respect to an antimorphic involution theta is a word which cannot be written as a catenation of occurrences of a strictly shorter word t and theta(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-Schutzenberger equation u(1) u(2) ... u(l) = v(1) ... v(n) w(1) ... w(m), where u(1),..., u(l) is an element of {u, theta(u)}, v(1),..., v(n) is an element of (v, theta(v)}, and w(1),..., w(m) is an element of {w, theta(w)} for some words u, v, w, integers l,n,m >= 2, and an antimorphic involution theta. We prove that for l >= 4, n, m >= 3, this equation implies that u, v, w can be expressed in terms of a common word t and its image theta(t). Moreover, several cases of this equation where l = 3 are examined.
研究論文（学術雑誌）, 英語 - Triangular Tile Self-assembly Systems
Lila Kari; Shinnosuke Seki; Zhi Xu
DNA COMPUTING AND MOLECULAR PROGRAMMING, SPRINGER-VERLAG BERLIN, 6518巻, 掲載ページ 89-99, 出版日 2011年, 査読付, We discuss theoretical aspects of the self-assembly of triangular tiles; in particular, right triangular tiles and equilateral triangular tiles. Contrary to intuition, we show that triangular tile assembly systems and square tile assembly systems are not comparable in general. More precisely, there exists a square tile assembly system S such that no triangular tile assembly system that is a division of S produces the same final supertile. There also exists a deterministic triangular tile assembly system T such that no square tile assembly system produces the same final supertiles while preserving border glues. We discuss the assembly of triangles by triangular tiles and show triangular systems with Theta(log N/log log N) tiles that can self-assemble into a triangular supertile of size Theta(N(2)). Lastly, we show that triangular tile assembly systems, either right-triangular or equilateral, are Turing universal.
研究論文（国際会議プロシーディングス）, 英語 - Scalable, Time-Responsive, Digital, Energy-Efficient Molecular Circuits Using DNA Strand Displacement
Ehsan Chiniforooshan; David Doty; Lila Kari; Shinnosuke Seki
DNA COMPUTING AND MOLECULAR PROGRAMMING, SPRINGER-VERLAG BERLIN, 6518巻, 掲載ページ 25-36, 出版日 2011年, 査読付, We propose a novel theoretical biomolecular design to implement any Boolean circuit using the mechanism of DNA strand displacement. The design is scalable: all species of DNA strands can in principle be mixed and prepared in a single test tube, rather than requiring separate purification of each species, which is a barrier to large-scale synthesis. The design is time-responsive: the concentration of output species changes in response to the concentration of input species, so that time-varying inputs may be continuously processed. The design is digital: Boolean values of wires in the circuit are represented as high or low concentrations of certain species, and we show how to construct a single-input, single-output signal restoration gate that amplifies the difference between high and low, which can be distributed to each wire in the circuit to overcome signal degradation. This means we can achieve a digital abstraction of the analog values of concentrations. Finally, the design is energy-efficient: if input species are specified ideally (meaning absolutely 0 concentration of unwanted species), then output species converge to their ideal concentrations at steady-state, and the system at steady-state is in (dynamic) equilibrium, meaning that no energy is consumed by irreversible reactions until the input again changes.
研究論文（国際会議プロシーディングス）, 英語 - ORTHOGONAL SHUFFLE ON TRAJECTORIES
Mark Daley; Lila Kari; Shinnosuke Seki; Petr Sosik
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, WORLD SCIENTIFIC PUBL CO PTE LTD, 22巻, 1号, 掲載ページ 213-222, 出版日 2011年01月, 査読付, A language L is called the orthogonal shuffle of the language L(1) with the language L(2), along the trajectory set T if every word in L is uniquely obtained as the shuffle between a word in L(1), a word in L(2) along a trajectory word in T. In this paper we investigate properties of the orthogonal shuffle on trajectories, as well as several types of language equations using this language operation. As a corollary, we obtain several properties of orthogonal catenation, orthogonal literal shuffle and orthogonal insertion.
研究論文（学術雑誌）, 英語 - K-Comma Codes and Their Generalizations
Bo Cui; Lila Kari; Shinnosuke Seki
FUNDAMENTA INFORMATICAE, IOS PRESS, 107巻, 1号, 掲載ページ 1-18, 出版日 2011年, 査読付, In this paper, we introduce the notion of k-comma codes-a proper generalization of the notion of comma-free codes. For a given positive integer k, a k-comma code is a set L over an alphabet Sigma with the property that L Sigma(k) L boolean AND Sigma(+) L Sigma(+) = empty set. Informally, in a k-comma code, no codeword can be a subword of the catenation of two other codewords separated by a "comma" of length k. A k-comma code is indeed a code, that is, any sequence of codewords is uniquely decipherable. We extend this notion to that of k-spacer codes, with commas of length less than or equal to a given k. We obtain several basic properties of k-comma codes and their generalizations, k-comma intercodes, and some relationships between the families of k-comma intercodes and other classical families of codes, such as infix codes and bifix codes. Moreover, we introduce the notion of n-k-comma intercodes, and obtain, for each k >= 0, several hierarchical relationships among the families of n-k-comma intercodes, as well as a characterization of the family of 1-k-comma intercodes.
研究論文（学術雑誌）, 英語 - On the Regularity of Iterated Hairpin Completion of a Single Word
Lila Kari; Shinnosuke Seki; Steffen Kopecki
FUNDAMENTA INFORMATICAE, IOS PRESS, 110巻, 1-4号, 掲載ページ 201-215, 出版日 2011年, 査読付, Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = x alpha y (alpha) over bar, and outputs w ' = x alpha y (alpha) over bar(x) over bar, where (x) over bar 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 alpha and (alpha) over bar 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 alpha and (alpha) over bar, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of alpha and (alpha) over bar, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.
研究論文（学術雑誌）, 英語 - The Power of Nondeterminism in Self-Assembly
Nathaniel Bryans; Ehsan Chiniforooshan; David Doty; Lila Kari; Shinnosuke Seki
PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SIAM, 掲載ページ 590-602, 出版日 2011年, 査読付, We investigate the role of nondeterminism in Winfree's abstract tile assembly model, which was conceived to model artificial molecular self-assembling systems constructed from DNA. By nondeterminism we do not mean a magical ability such as that possessed by a nondeterministic algorithm to search an exponential-size space in polynomial time. Rather, we study realistically implementable systems that retain a different sense of determinism in that they are guaranteed to produce a unique shape but are nondeterministic in that they do not guarantee which tile types will be placed where within the shape.
We show a "molecular computability" result: there is an infinite shape S that is uniquely assembled by a tile system but not by any deterministic tile system. We show a "molecular complexity" result: 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 is NP-complete [5].
研究論文（国際会議プロシーディングス）, 英語 - One-Reversal Counter Machines and Multihead Automata: Revisited
Ehsan Chiniforooshan; Mark Daley; Oscar H. Ibarra; Lila Kari; Shinnosuke Seki
SOFSEM 2011: THEORY AND PRACTICE OF COMPUTER SCIENCE, SPRINGER-VERLAG BERLIN, 6543巻, 掲載ページ 166-177, 出版日 2011年, 査読付, Among the many models of language acceptors that have been studied in the literature are multihead finite automata (finite automata with multiple one-way input heads) and 1-reversal counter machines (finite automata with multiple counters, where each counter can only "reverse" once, i.e., once a counter decrements, it can no longer increment). The devices can be deterministic or nondeterministic and can be augmented with a pushdown stack. We investigate the relative computational power of these machines. Our results (where C-1 and C-2 are classes of machines) are of the following types:
1. Machines in C-1 and C-2 are incomparable.
2. Machines in C-1 are strictly weaker than machines in C-2.
In obtaining results of these types, we use counting and "cut-and-paste" arguments as well as an interesting technique that shows that if a language were accepted by a device in a given class, then all recursively enumerable languages would be decidable.
研究論文（国際会議プロシーディングス）, 英語 - Characterizations of bounded semilinear languages by one-way and two-way deterministic machines
Oscar H. Ibarra; Shinnosuke Seki
AFL 2011: Proceedings of the 13th International Conference on Automata and Formal Languages, 掲載ページ 211-224, 出版日 2011年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Program Size and Temperature in Self-assembly
Ho-Lin Chen; David Doty; Shinnosuke Seki
ALGORITHMS AND COMPUTATION, SPRINGER-VERLAG BERLIN, 7074巻, 掲載ページ 445-+, 出版日 2011年, 査読付, Winfree's abstract Tile Assembly Model (aTAM) is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing "seed" assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an n x n square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman, Cheng, God, Huang, Kempe, Moisset de Espanes, and Rothemund (Combinatorial Optimization Problems in Self-Assembly, STOC 2002). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its "temperature" (the binding strength threshold required for a tile to attach).
研究論文（国際会議プロシーディングス）, 英語 - On a special class of primitive words
Elena Czeizler; Lila Kari; Shinnosuke Seki
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 411巻, 3号, 掲載ページ 617-630, 出版日 2010年01月, 査読付, When representing DNA molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its Watson-Crick complement theta(u), where theta denotes the Watson-Crick complementarity function. Thus, an expression which involves only a word u and its complement can be still considered as a repeating sequence. In this context, we define and investigate the properties of a special class of primitive words, called pseudo-primitive words relative to theta or simply theta-primitive words, which cannot be expressed as such repeating sequences. For instance, we prove the existence of a unique theta-primitive root of a given word, and we give some constraints forcing two distinct words to share their theta-primitive root. Also, we present an extension of the well-known Fine and Wilf theorem, for which we give an optimal bound. (C) 2009 Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - An Improved Bound for an Extension of Fine and Wilf's Theorem and Its Optimality
Lila Kari; Shinnosuke Seki
FUNDAMENTA INFORMATICAE, IOS PRESS, 101巻, 3号, 掲載ページ 215-236, 出版日 2010年, 査読付, Considering two DNA molecules which are Watson-Crick (WK) complementary to each other "equivalent" with respect to the information they encode enables us to extend the classical notions of repetition, period, and power. WK-complementarity has been modelled mathematically by an antimorphic involution theta, i.e., a function theta such that theta( xy) = theta(y)theta(x) for any x, y is an element of Sigma*, and theta(2) is the identity. The WK-complementarity being thus modelled, any word which is a repetition of u and theta(u) such as u u, u theta(u)u, and u theta(u)theta(u)theta(u) can be regarded repetitive in this sense, and hence, called a theta-power of u. Taking the notion of theta-power into account, the Fine and Wilf's theorem was extended as "given an antimorphic involution theta and words u, v, if a theta-power of u and a theta-power of v have a common prefix of length at least b (vertical bar u vertical bar, vertical bar v vertical bar) = 2 vertical bar u vertical bar + vertical bar v vertical bar - gcd (vertical bar u vertical bar, vertical bar v vertical bar), then u and v are theta-powers of a same word." In this paper, we obtain an improved bound b' (vertical bar u vertical bar, vertical bar v vertical bar) = b (vertical bar u vertical bar, vertical bar v vertical bar) -[gcd (vertical bar u vertical bar, vertical bar v vertical bar)/2.. Then we show all the cases when this bound is optimal by providing all the pairs of words (u,v) such that they are not theta-powers of a same word, but one can construct a theta-power of u and a theta-power of v whose maximal common prefix is of length equal to b'(vertical bar u vertical bar, vertical bar v vertical bar) - 1. Furthermore, we characterize such words in terms of Sturmian words.
研究論文（学術雑誌）, 英語 - Schema for Parallel Insertion and Deletion
Lila Kari; Shinnosuke Seki
DEVELOPMENTS IN LANGUAGE THEORY, SPRINGER-VERLAG BERLIN, 6224巻, 掲載ページ 267-278, 出版日 2010年, 査読付, We propose a general framework for parallel insertion/deletion operations based on p-schemata. A p-schema is a set of tuples of words. When being used for parallel insertion of a language into a word, an element of a p-schema specifies how to split the given word into factors between which the insertion of the language will take place. Parallel deletion based on a p-schema is defined as an "inverse" operation of parallel insertion based on the p-schema. Several well-known language operations are particular cases of p-schema-based insertions or deletions: catenation, Kleene star, reverse catenation, sequential insertion, parallel insertion, insertion next to a given letter, contextual insertion, right and left quotient, sequential deletion, parallel deletion. Additional operations that can be defined using p-schemata include contextual parallel insertion, as well as parallel insertion (deletion) of exactly n words, at most n words, an arbitrary number of words. We also consider the decidability and undecidability of existence of solutions of language equations involving p-schema-based parallel insertion/deletion.
研究論文（国際会議プロシーディングス）, 英語 - Twin-roots of words and their properties
Lila Kari; Kalpana Mahalingam; Shinnosuke Seki
THEORETICAL COMPUTER SCIENCE, ELSEVIER SCIENCE BV, 410巻, 24-25号, 掲載ページ 2393-2400, 出版日 2009年05月, 査読付, In this paper we generalize the notion of an iota-symmetric word, from an antimorphic involution, to an arbitrary involution iota as follows: a nonempty word w is said to be iota-symmetric if w = alpha beta = iota(beta alpha) for some words alpha, beta. We propose the notion of iota-twin-roots (x, y) of an iota-symmetric word w. We prove the existence and uniqueness of the iota-twin-roots of ail iota-symmetric word, and show that the left factor alpha and right factor beta of any factorization of w as w = alpha beta = iota(beta alpha), can be expressed in terms of the iota-twin-roots of w. In addition, we show that for any involution iota, the catenation of the iota-twin-roots of w equals the primitive root of w. We also provide several characterizations of the iota-twin-rots of a word, for iota being a morphic or antimorphic involution. Crown Copyright (C) 2009 Published by Elsevier B.V. All rights reserved.
研究論文（学術雑誌）, 英語 - On pseudoknot-bordered words and their properties
Lila Kari; Shinnosuke Seki
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, ACADEMIC PRESS INC ELSEVIER SCIENCE, 75巻, 2号, 掲載ページ 113-121, 出版日 2009年02月, 査読付, We Study a generalization of the classical notions of [)ordered and unbordered words, motivated by biomolecular Computing. DNA strands can be viewed as finite strings over the alphabet [A, G, C, T), and are used in biomolecular computing to encode information. Due to the fact that A is Witson-Crick complementary to T and G to C, DNA single strands that are Watson-Crick complementary can bind to each other or to themselves forming so-called secondary structures, Most of these secondary structures are undesirable for biomolecular computational purposes since the strands they involve cannot further interact with other strands. This paper studies pseudoknot-bordered words, a mathematical formalization of pseudoknot-like inter- and intra-molecular structures. In this context, pseudoknot-unbordered words model DNA or RNA strands that will be free of such secondary structures. We obtain several properties of pseudoknot-bordered and -unbordered words. We also address Following problem: Given a pseudoknot-unbordered word u, does {u}(+) consist of pseudoknot-unbordered words only? We show that this is not generally true. We find that a sufficient condition for {u}(+) to consist of pseudoknot-unbordered words only is that it be not primitive. All of our results hold for arbitrary antimorphic involutions, of which the DNA Watson-Crick complementarity function is a particular case. Crown Copyright (c) 2008 Published by Elsevier Inc. All rights reserved.
研究論文（学術雑誌）, 英語 - An Efficient Multiple Alignment Method for RNA Secondary Structures Including Pseudoknots
Shinnosuke Seki; Satoshi Kobayashi
NATURAL COMPUTING, PROCEEDINGS, SPRINGER, 1巻, 掲載ページ 179-+, 出版日 2009年, 査読付, Pseudoknots, one of the key components of RNA secondary structures, have been almost systematically intractable because of the difficulty in modeling them. Tree adjoining grammars have proved to be promising for this problem but the question of how to make TAG-based applications practical enough to analyze RNAs of thousands nucleotides remains open. This paper addresses this problem. It makes use of biological properties of pseudoknots, the scarcity and short-bp property. Experiments showed that our algorithm can align RNAs of the length tip to about 2400 nucleotides with biologically meaningful outputs extremely fast on the standard workstation environment. An executable version of our implementation is available at http://www.csd.uwo.ca/(similar to)sseki/
研究論文（国際会議プロシーディングス）, 英語 - Towards the Sequence Design Preventing Pseudoknot Formation
Lila Kari; Shinnosuke Seki
NATURAL COMPUTING, PROCEEDINGS, SPRINGER, 1巻, 掲載ページ 101-110, 出版日 2009年, 査読付, This paper addresses a pseudoknot-freeness problem of DNA and RNA sequences, motivated by biomolecular computing. Watson-Crick (WK) complementarity forces DNA strands to fold into themselves and form so-called secondary structures, which are usually undesirable for biomolecular computational purposes. This paper studies pseudoknot-bordered words, a mathematical formalization of a common secondary structure, the pseudoknot. We obtain several properties of WK-pseudoknot-bordered and -unbordered words. One of the main results of the paper is that a sufficient condition for a WK-pseudoknot-unbordered word u to result in all words in u(+) being WK-pseudoknot-unbordered is for u not to be a primitive word.
研究論文（国際会議プロシーディングス）, 英語 - Duplication in DNA Sequences
Masami Ito; Lila Kari; Zachary Kincaid; Shinnosuke Seki
ALGORITHMIC BIOPROCESSES, SPRINGER-VERLAG BERLIN, LNCS 5257巻, 掲載ページ 43-+, 出版日 2009年, 査読付, The duplication and repeat-deletion operations are the basis of a formal language theoretic model of errors that can occur during DNA replication. During DNA replication, subsequences of a strand of DNA may be copied several times (resulting in duplications) or skipped (resulting in repeat-deletions). As formal language operations, iterated duplication and repeat-deletion of words and languages have been well studied in the literature. However, little is known about single-step duplications and repeat-deletions. In this paper, we investigate several properties of these operations, including closure properties of language families in the Chomsky hierarchy and equations involving these operations. We also make progress toward a characterization of regular languages that are generated by duplicating a regular language.
研究論文（国際会議プロシーディングス）, 英語 - On the Reversibility of Parallel Insertion, and Its Relation to Comma Codes
Bo Cui; Lila Kari; Shinnosuke Seki
ALGEBRAIC INFORMATICS, SPRINGER-VERLAG BERLIN, 5725巻, 掲載ページ 204-219, 出版日 2009年, 査読付, This paper studies Conditions under which the operation of parallel insertion can be reversed by parallel deletion. i.e.. when does the equality (L(1) double left arrow L(2)) double right arrow L(2) = L(1) hold for languages L(1) and L(2). We obtain a complete characterization of the solutions in the special M. se when both languages involved are singleton words. We also define comma codes, a family of codes with the property that, if L(2) is a comma code, then the above equation holds for any language L(1) subset of Sigma*. Lastly, we generalize the notion of comma codes to that of comma intercodes of index m. Besides several properties, we prove that the families of comma intercedes of index m form an infinite proper inclusion hierarchy, the first element which is a subset of the family of infix codes, and the last element of which is a subset of the family of bifix codes.
研究論文（国際会議プロシーディングス）, 英語 - An Extension of the Lyndon Schutzenberger Result to Pseudoperiodic Words
Elena Czeizler; Eugen Czeizler; Lila Kari; Shinnosuke Seki
DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5583巻, 掲載ページ 183-+, 出版日 2009年, 査読付, One of the particularities of information encoded as DNA strands is that a string u contains basically the same information as its Watson-Crick complement, denoted here as theta(u). Thus, any expression consisting of repetitions of u and theta(u) can be considered in some sense periodic. In this paper we give a generalization of Lyndon and Schutzenberger's classical result about equations of the form u(l) = upsilon(n)omega(m), to cases where both sides involve repetitions of words as well as their complements. Our main results show that, for such extended equations, if l >= 5, n, m >= 3, then all three words involved can be expressed in terms of a common word t and its complement theta(t). Moreover. if l >= 5, then n = m = 3 is an optimal bound. We also obtain a complete characterization of all possible overlaps between two expressions that involve only some word u and its complement theta(u).
研究論文（国際会議プロシーディングス）, 英語 - On a special class of primitive words
Elena Czeizler; Lila Kari; Shinnosuke Seki
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2008, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 5162巻, 掲載ページ 265-277, 出版日 2008年, 査読付, When representing DNA molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its Watson-Crick complement theta(u), where theta denotes the Watson-Crick complementarity function. Thus, an expression which involves only a word u and its complement can be still considered as a, repeating sequence. In this context, we define and investigate the properties of a special class of primitive words, called theta-primitive, which cannot be expressed as such repeating sequences. For instance, we prove the existence of a unique theta-primitive root of a given word, and we give some constraints forcing two distinct words to share their theta-primitive root. Also, we present an extension of the well-known Fine and Wilf Theorem, for which we give an optimal bound.
研究論文（国際会議プロシーディングス）, 英語 - A grammatical approach to the alignment of structure-annotated strings
S Seki; S Kobayashi
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E88D巻, 12号, 掲載ページ 2727-2737, 出版日 2005年12月, 査読付, In this paper, we are concerned with a structural ambiguity problem of tree adjoining grammars (TAGS), which is an essential problem when we try to model consensus structures of given set of ribonucleic acid (RNA) secondary structures by TAGS. RNA secondary structures can be represented as strings with structural information, and TAGS have a descriptive capability of this kind of strings, what we call structure-annotated strings. Thus, we can model RNA secondary structures by TAGs. It is sufficient to use existing alignment methods for just computing the optimal alignment between RNA secondary structures. However, when we also want to model the resulting alignment by grammars, if we adopt these existing methods, then we may fail in modeling the alignment result by grammars. Therefore, it is important to introduce a new alignment method whose alignment results can be appropriately modeled by grammars. In this paper, we will propose an alignment method based on TAG'S derivations each corresponding to a given RNA secondary structure. For an RNA secondary structure, there exist a number of derivations of TAGS which correspond to the structure. From the grammatical point of view, the property of TAGS drives us to the question how we should choose a derivation from these candidates in order to obtain an optimal alignment. This is the structural ambiguity problem of TAGS, which will be mainly discussed in this paper. For dealing with this problem appropriately, we will propose an edit distance between two structure-annotated strings, and then present an algorithm which computes an optimal alignment based on the edit distance.
研究論文（学術雑誌）, 英語 - Efficient learning of k-reversible context-free grammars from positive structural examples
S Seki; S Kobayashi
GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS, PROCEEDINGS, SPRINGER-VERLAG BERLIN, 3264巻, 掲載ページ 285-287, 出版日 2004年, 査読付, This paper discusses on the learnability of context free grammars(CFGs) within the framework of identification in the limit from positive structural examples. We will introduce a new subclass of CFGs, called a class of k-reversible context-free grammars and propose an O(kdn(3)) algorithm for learning this new subclass of CFGs, where d is the maximum of the ranks of given skeletal trees, and n is the total size of the given examples.
研究論文（学術雑誌）, 英語 - Hierarchical Alignment of RNA secondary structures including pseudoknots
Shinnosuke Seki; Atsushi Kijima; Satoshi Kobayashi; Genichi Sanpei
GIW 2004: Proceedings of the 15th International Conference on Genome Informatics, 掲載ページ 117-1-117-2, 出版日 2004年, 査読付
研究論文（国際会議プロシーディングス）, 英語
MISC
- RNA折り紙
関 新之助
筆頭著者, 出版日 2019年, 電子情報通信学会誌, 102巻, 4号, 掲載ページ 330-334, 日本語, 査読付, 招待 - Cotranscriptional folding: A frontier in molecular engineering a challenge for computer scientists
Shinnosuke Seki
SIAM (Society for Industrial and Applied Mathematics), 出版日 2017年05月01日, SIAM News, Not assigned yet巻, 英語, 査読付, 記事・総説・解説・論説等（学術雑誌）
書籍等出版物
- Special issue of New Generation Computing devoted to Hagiya-sensei's 64th birthday.
英語, 共編者(共編著者), Springer, 出版日 2022年08月 - Special issue of Natural Computing devoted to the International Conference on Unconventional Computation and Natural Computation (UCNC 2019)
Ian McQuillan; Shinnosuke Seki
英語, 共編者(共編著者), Springer, 出版日 2021年 - Special issue of International Journal of Foundations of Computer Science (IJFCS) devoted to Developments in Language Theory 2018
Shinnosuke Seki
英語, 編者(編著者), World Scientific, 出版日 2020年09月 - Proceedings of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC2019, Tokyo, Japan, June 3-7, 2019)
英語, 共編者(共編著者), Springer, 出版日 2019年 - Proceedings of the 18th International Conference on Unconventional Computation and Natural Computation
英語, 共編者(共編著者), Springer, 出版日 2019年 - Proceedings of the 22nd International Conference on Developments in Language Theory (DLT2018, Tokyo, Japan, September 10-14, 2018)
学術書, 英語, 共編者(共編著者), Springer, 出版日 2018年08月06日 - Encyclopedia of Algorithms
Shinnosuke Seki
事典・辞書, 英語, 単著, Patterned Self-Assembly Tile Set Synthesis, Springer, 出版日 2016年 - 自然計算についてのハンドブック
Lila Kari; Shinnosuke Seki; Petr Sosik
学術書, 英語, 分担執筆, Springer, 出版日 2012年 - 言語理論の進展に関する第１４回国際会議紀要
Yuan Gao; Hanlin Lu; Shinnosuke Seki; Sheng Yu
学術書, 英語, 編者(編著者), Springer, 出版日 2010年
講演・口頭発表等
- How complex shapes can RNA fold into?
Shinnosuke Seki
口頭発表（招待・特別）, 英語, 17th International Conference on Reachability Problems (RP 2023), 招待, 査読付
発表日 2023年10月13日
開催期間 2023年10月11日- 2023年10月13日 - Freezing 1-Tag systems with states
Szilard Zsolf Fazekas
口頭発表（一般）, 英語, 16th International Conference on Automata and Formal Languages (AFL 2023), 査読付
発表日 2023年09月06日
開催期間 2023年09月05日- 2023年09月07日 - On algorithmic self-assembly of squares by co-transcriptional folding
Ryuichi Matsuoka
口頭発表（一般）, 英語, The 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Hanyang University, Seoul, Republic of Korea, 査読付
発表日 2022年12月20日
開催期間 2022年12月19日- 2022年12月21日 - Single-stranded architectures for computing by RNA co-transcriptional folding
Shinnosuke Seki
公開講演，セミナー，チュートリアル，講習，講義等, 英語, 招待, Ajou University, Suwon, Republic of Korea
発表日 2022年12月15日 - Single-stranded architectures for RNA co-transcriptional folding
Shinnosuke Seki
口頭発表（招待・特別）, 英語, Moving and Computing 2022 (MaC2022), 招待, University of Pisa, Pisa, Italy, 国際会議
発表日 2022年09月19日 - Single-stranded architectures for RNA co-transcriptional folding
Shinnosuke Seki
口頭発表（招待・特別）, 英語, Dagstuhl seminar 22381: Rational Design of Ribonucleic Acids, 招待, Schloss Dagstuhl, Dagstuhl, Germany, 国際会議
発表日 2022年09月19日 - Turedo a new computational model for molecular nanobots?
Nicolas Schabanel
口頭発表（招待・特別）, 英語, Computability in Europe (CiE 2022), 招待, Swansea University, 国際会議
発表日 2022年07月14日 - Oritatami systems assemble shapes no less complex than tile assembly model
Nicolas Schabanel
口頭発表（一般）, 英語, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), 国際会議
発表日 2022年03月15日 - Algorithmic self-assembly of squares in oritatami
松岡 龍一
口頭発表（一般）, 英語, 2021年度 冬のLAシンポジウム, 京都大学数理解析研究所, 国内会議
発表日 2021年02月01日 - Simple intrinsic simulation of cellular automata in oritatami molecular folding model
Daria Pchelina
口頭発表（一般）, 英語, 14th Latin American Symposium on Theoretical Informatics (LATIN 2020), 招待, 国際会議
発表日 2021年01月05日 - Les oritatamis tracent des dessins indécidables
Nicolas Schabanel
口頭発表（一般）, フランス語, Journées SDA2 2020: Systèmes Dynamiques, Automates et Algorithmes, Caen, France, 国際会議
発表日 2020年12月04日 - Single-stranded architectures for computing
Shinnosuke Seki
口頭発表（一般）, 英語, 1st International Conference on Information Technology and Data Science, 招待, University of Debrecen, Debrecen, Hungary, 国際会議
発表日 2020年11月06日 - A single-stranded architecture for infinite counting
Shinnosuke Seki
公開講演，セミナー，チュートリアル，講習，講義等, 英語, 招待, Politecnico di Torino (Torino, Italy)
発表日 2020年01月27日 - Counting infinitely by oritatami co-transcriptional folding
Kohei Maruyama
口頭発表（一般）, 英語, SOFSEM2020: 46th International Conference on Current Trends in Theory and Practice of Informatics, Limassol, Cyprus, 国際会議
発表日 2020年01月20日 - Single-stranded architectures for computing
Shinnosuke Seki
口頭発表（招待・特別）, 英語, 23rd International Conference on Developments in Language Theory (DLT 2019), 招待, University of Warsaw, Warsaw, Poland, 国際会議
発表日 2019年08月05日 - A general architecture of oritatami systems for simulating arbitrary finite automata
Shinnosuke Seki
口頭発表（一般）, 英語, CIAA2019: 24th International Conference on Implementation and Application of Automata, Slovak Academy of Science, Kosice, Slovakia, 国際会議
発表日 2019年07月22日 - On the power of oritatami cotranscriptional folding with unary bead sequence
Kohei Maruyama; Reoto Morita
口頭発表（一般）, 英語, TAMC2019: 15th Annual Conference on Theory and Applications of Models of Computation, 国際会議
発表日 2019年04月13日 - Proving the Turing universality of oritatami cotranscriptional folding
Nicolas Schabanel
口頭発表（一般）, 英語, 29th International Symposium on Algorithms and Computation (ISAAC2018), 国際会議
発表日 2018年12月16日 - Know when to fold 'em: Self-assembly of shapes by folding in oritatami
Nicolas Schabanel
口頭発表（一般）, 英語, DNA24: 24th International Conference on DNA Computing and Molecular Programming, 国際会議
発表日 2018年10月08日 - Transcript desing problem of oritatami systems
Hwee Kim
口頭発表（一般）, 英語, DNA24: 24th International Conference on DNA Computing and Molecular Programming, 国際会議
発表日 2018年10月08日 - Towards the algorithmic molecular self-assembly of fractals by cotranscriptional folding
Yusei Masuda; Yuki Ubukata
口頭発表（一般）, 英語, 23rd International Conference on Implementation and Application of Automata (CIAA 2018), 国際会議
発表日 2018年07月30日 - Proving Turing universality of cotranscriptional folding
Shinnosuke Seki
口頭発表（一般）, 英語, 2018 Zassenhaus Groups and Friends Conference, 招待, University of South Florida, Tampa, FL, USA, 国際会議
発表日 2018年04月06日 - Self-Assembly of shapes by cotranscriptional folding
Shinnosuke Seki
口頭発表（一般）, 英語, 招待, Department of Mathematics and Statistics, University of South Florida
発表日 2018年04月02日 - Cotranscriptional Folding: A Frontier in Molecular Engineering
Shinnosuke Seki
口頭発表（一般）, 英語, 京都大学数理解析研究所RIMS共同研究（公開型）「代数系、論理、言語とその周辺領域」, 国内会議
発表日 2018年02月20日 - Proving Turing universality of cotranscriptional folding
Shinnosuke Seki
口頭発表（一般）, 日本語, 京都大学数理解析研究所RIMS共同研究（公開型）「アルゴリズムと計算理論の基礎と応用」, 国内会議
発表日 2018年02月05日 - Turing completeness of RNA cotarnsccriptional folding
Shinnosuke Seki
口頭発表（招待・特別）, 英語, SICE Molecular Robotics Seminar, 4th JST Seminar on Ethical Issues for Molecular Robots, 招待, Hakata, Japan, 国内会議
発表日 2018年01月19日 - Self-attraction removal from oritatami systems
Hwee Kim
口頭発表（一般）, 英語, 19th International Conference on Descriptional Complexity of Formal Systems, Milan, Italy, 国際会議
発表日 2017年07月03日 - Bit string bifurcation by cotranscriptional folding
Yusei Masuda; Yuki Ubukata
口頭発表（一般）, 英語, 1st International Workshop on Oritatami, Shinnosuke Seki, University of Arkansas, 国際会議
発表日 2017年06月06日 - Bit string bifurcation by cotranscriptional folding
Yusei Masuda; Yuki Ubukata
口頭発表（一般）, 英語, 11th International Workshop on Natural Computing, Akita International University, 国際会議
発表日 2017年05月13日 - Self-assembly at nano scale by molecular Xerox
Shinnosuke Seki
口頭発表（招待・特別）, 英語, 11th International Workshop on Natural Computing, 招待, Akita International University, Akita, Japan, 国際会議
発表日 2017年05月13日 - 分子コピー機を用いたナノスケール自己組織化
関 新之助
口頭発表（一般）, 日本語, 第2回 若手研究者のための熱利用・環境技術ワークショップ, 招待, 化学工学会エネルギー部会熱利用分科会, 東京都八王子市, 国内会議
発表日 2016年12月02日 - Oritatami, a novel frontier in molecular self-assembly
Shinnosuke Seki
口頭発表（招待・特別）, 英語, 招待, Yonsei University
発表日 2016年11月21日 - Oritatami, a novel mathematical model of RNA cotranscriptional folding
Shinnosuke Seki
公開講演，セミナー，チュートリアル，講習，講義等, 英語, 招待, Akita University, Akita, Japan
発表日 2016年10月20日 - Nondeterministic seedless oritatami systems and hardness of testing their equivalence
Hwee Kim
口頭発表（一般）, 英語, The 22nd International Conference on DNA Computing and Molecular Programming (DNA 22), Munich, Germany, 国際会議
発表日 2016年09月04日 - Programming biomolecules that fold greedily during transcription
Pierre-Etienne Meunier
口頭発表（一般）, 英語, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), 国際会議
発表日 2016年08月22日 - The complexity of fixed-height patterned tile self-assembly
Shinnosuke Seki
口頭発表（一般）, 英語, 21st International Conference on Implementation and Application of Automata (CIAA 2016), Seoul, Republic of Korea, 国際会議
発表日 2016年07月19日 - Folding Turing is hard but feasible
Nicolas Schabanel
口頭発表（一般）, 英語, Highlights of Algorithms (HALG 2016), Paris, France, 国際会議
発表日 2016年06月06日 - Molecular cotranscriptional folding: A novel challenge in theory and applications of self-assembly
Shinnosuke Seki
公開講演，セミナー，チュートリアル，講習，講義等, 英語, 招待, University of South Florida, Tampa, Florida, USA
発表日 2016年01月25日 - Molecular cotranscriptional folding: A novel topic in theory and applications of self-assembly
関 新之助
口頭発表（招待・特別）, 英語, 5th Interdisciplinary Research and Global Outlook (IRAGO2015)
発表日 2015年10月22日 - Square-density increasing mappings
関 新之助
口頭発表（一般）, 英語, 10th International Conference on Combinatorics on Words (WORDS2015), 国際会議
発表日 2015年09月14日 - Computational complexity of inverse word search problem
Hiro Ito
口頭発表（一般）, 英語, 12th International Symposium on Operations Research and Its Applications (ISORA2015), 国際会議
発表日 2015年08月21日 - Efficient universal computation by molecular cotranscriptional folding
Shinnosuke Seki
口頭発表（一般）, 英語, 21st International Conference on DNA Computing and Molecular Programming (DNA21), Wyss Institute for Biologically inspired Engineering at Harvard University, 国際会議
発表日 2015年08月17日 - Binary pattern tile set synthesis is NP-hard
関 新之助
口頭発表（一般）, 英語, 42nd International Colloquium on Automata, Languages, and Programming (ICALP2015), 国際会議
発表日 2015年07月04日 - 折り畳み：共転写性フォールディングの数理モデル
関 新之助
公開講演，セミナー，チュートリアル，講習，講義等, 英語, 招待, Turku, Finland, 国際会議
発表日 2015年03月04日 - 一般化Lyndon-Schutzenberger方程式
Florin Manea
口頭発表（一般）, 英語, MFCS2014: 39th International Symposium on Mathematical Foundations of Computer Science, Budapest, Hungary, 国際会議
発表日 2014年08月25日 - パリキ合同に基づく操作の状態複雑性
関 新之助
シンポジウム・ワークショップパネル（公募）, 英語, DCFS2014: 16th International Workshop on Descriptional Complexity of Formal Systems, Turku, Finland, 国際会議
発表日 2014年08月05日 - DNA pattern self-assembly: Introduction and recent breakthroughs
Nicolas Schabanel
口頭発表（招待・特別）, 英語, Complexite et Algorithmes: Algorithmes naturels, 招待, Universite Paris Diderot, LIAFA, Paris, France, 国際会議
発表日 2014年06月09日 - Stronger square conjecture on binary words
関 新之助
口頭発表（一般）, 英語, SOFSEM2014: 40th International Conference on Current Trends in Theory and Practice of Computer Science, 国際会議
発表日 2014年01月25日 - A stronger square conjecture on binary words
関 新之助
口頭発表（招待・特別）, 英語, 招待, Slovak Academy of Science, Kosice, Slovakia
発表日 2014年01月24日 - Computing minimum tile sets to self-assembly color patterns
Aleck Johnson
口頭発表（一般）, 英語, ISAAC2013: 24th International Symposium on Algorithms and Computation, Hong Kong, 国際会議
発表日 2013年12月16日 - How many repetitions can you put on a sequence?
関 新之助
口頭発表（招待・特別）, 英語, 招待, University of North Florida, Jacksonville, FL, USA
発表日 2013年11月07日 - Combinatorial optimization in pattern-assembly
関 新之助
口頭発表（招待・特別）, 英語, 招待, University of North Florida, Jacksonville, FL, USA
発表日 2013年11月06日 - Combinatorial optimization in pattern-assembly
関 新之助
口頭発表（招待・特別）, 英語, 招待, Northwestern University, Evanston, IL, USA
発表日 2013年10月13日 - 3-color bounded patterned self-assembly
Steffen Kopecki
口頭発表（一般）, 英語, DNA 19: 19th International Conference on DNA Computing and Molecular Programming, Tempe, Arizona, USA, 国際会議
発表日 2013年09月22日 - Combinatorial optimization in pattern assembly (extended abstract)
関 新之助
口頭発表（一般）, 英語, UCNC2013: 12th International Conference on Unconventional Computation and Natural Computation, Milan, Italy, 国際会議
発表日 2013年07月01日 - On the boundedness property of semilinear sets
関 新之助
口頭発表（一般）, 英語, TAMC2013: 10th Annual Conference on Theory and Applications of Models of Computation, Hong Kong, 国際会議
発表日 2013年05月20日 - DNA pattern self-assembly
関 新之助
口頭発表（招待・特別）, 英語, 招待, Yonsei University, Seoul, Republic of Korea
発表日 2013年05月15日 - DNA pattern self-assembly
関 新之助
口頭発表（招待・特別）, 英語, Helsinki Institute for Information Technology (HIIT), Helsinki, Finland
発表日 2013年04月24日 - Roles that temperature plays in self-assembly
関 新之助
口頭発表（招待・特別）, 英語, 招待, University of South Florida, Tampa, FL, USA
発表日 2012年11月30日 - Combinatorial optimization in pattern assembly
関 新之助
口頭発表（招待・特別）, 英語, 招待, California Institute of Technology, Pasadena, California, USA
発表日 2012年11月02日 - Descriptional complexity in Parikh equivalence
関 新之助
口頭発表（招待・特別）, 英語, 招待, University of Western Ontario, London, ON, Canada
発表日 2012年10月18日 - Conveting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata
Giovanni Pighizzini
口頭発表（一般）, 英語, DLT2012: 16th International Conference on Developments in Language Theory, Taipei, Taiwan, 国際会議
発表日 2012年08月14日 - On the behavior of tile assembly system at high temperatures
関 新之助
口頭発表（一般）, 英語, CiE2012: Turing Centenary Conference - How the World Computes, Cambridge, UK, 国際会議
発表日 2012年06月18日 - Triangular and hexagonal tile self-assembly systems
Zhi Xu
口頭発表（一般）, 英語, WTCS2012: International Workshop on Theoretical Computer Science, Auckland, New Zealand, 国際会議
発表日 2012年02月21日 - On the behavior of tile assembly system at high temperatures
関 新之助
口頭発表（招待・特別）, 英語, Slovak Academy of Science, Kosice, Slovakia
発表日 2012年01月30日 - Iterated hairpin completions of non-crossing words
関 新之助
口頭発表（一般）, 英語, SOFSEM2012: 38th International Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Mlyn, Czech Republic, 国際会議
発表日 2012年01月21日 - In the century of communication
関 新之助
口頭発表（招待・特別）, 英語, 招待, 島根大学, 松江、日本
発表日 2011年12月13日 - Program size and temperature in self-assembly
David Doty
口頭発表（一般）, 英語, ISAAC2011: 22nd International Symposium on Algorithms and Computation, Yokohama, Japan, 国際会議
発表日 2011年12月05日 - Roles that temperature play in self-assembly
関 新之助
口頭発表（招待・特別）, 英語, 招待, University of Western Ontario, London, ON, Canada
発表日 2011年11月10日 - Number theory and computational efficiency in chemoinformatics
関 新之助
口頭発表（招待・特別）, 英語, 招待, University of Western Ontario, London, ON, Canada
発表日 2011年11月03日 - Number theory and computational efficiency in chemoinformatics
関 新之助
口頭発表（招待・特別）, 英語, 招待, University of Pavol Jozef Safarik, Kosice, Slovakia
発表日 2011年08月25日 - An introduction to the world of self-assembly
関 新之助
口頭発表（招待・特別）, 英語, 招待, Slovak Academy of Science, Kosice, Slovakia
発表日 2011年08月24日 - Characterizations of bounded semilinear languages by one-way and two-way deterministic machines
関 新之助
口頭発表（一般）, 英語, AFL2011: 13th International Conference on Automata and Formal Languages, Debrecen, Hungary, 国際会議
発表日 2011年08月20日 - Scalable, time-responsive, digital, energy-efficient, moleculer circuits using DNA strand displacement
David Doty
ポスター発表, 英語, DNA16: 16th International Conference on DNA Computing and Molecular Programming, Hong Kong, 国際会議
発表日 2011年06月14日 - One-reversal counter machines and multihead automata: revisited
関 新之助
口頭発表（一般）, 英語, SOFSEM2011: 37th International Conference on Current Trends in Theory and Practice of Computer Science, High Tatras, Slovakia, 国際会議
発表日 2011年01月22日 - Power of nondeterminism in self-assembly
David Doty
口頭発表（一般）, 英語, SODA2011: ACM-SIAM Symposium on Discrete Algorithms, San Fransisco, California, USA, 国際会議
発表日 2011年01月22日 - Schema for parallel insertion and deletion
関 新之助
口頭発表（一般）, 英語, DLT2010: 14th International Conference on Developments in Language Theory, London, ON, Canada, 国際会議
発表日 2010年08月17日 - Triangular tile self-assembly systems
関 新之助
ポスター発表, 英語, DNA16: 16th International Conference on DNA Computing and Molecular Programming, Hong Kong, 国際会議
発表日 2010年06月14日 - Schema for parallel insertion and deletion
関 新之助
口頭発表（招待・特別）, 英語, Workshop on Formal Languages and Automata III, 招待, 京都産業大学, Kyoto, Japan, 国際会議
発表日 2009年12月12日 - An extension of fundamental notions in combinatorics on words inspired by DNA information encoding
関 新之助
口頭発表（招待・特別）, 英語, 招待, Universitate Potsdam, Potsdam, Germany
発表日 2009年07月06日 - An extension of the Lyndon-Schutzenberger result to pseudoperiodic words
関 新之助
口頭発表（一般）, 英語, DLT2009: 13th International Conference on Developments in Language Theory, Stuttgard, Germany, 国際会議
発表日 2009年06月30日 - On the reversibility of parallel insertion, and its relation to comma codes
Bo Cui
口頭発表（一般）, 英語, CAI2009: 3rd International Conference on Algebraic Informatics, Thessaloniki, Greece, 国際会議
発表日 2009年05月19日 - Duplication in DNA sequences
Zachary Kincaid
口頭発表（一般）, 英語, DLT2008: 12th International Conference on Developments in Language Theory, Kyoto, Japan, 国際会議
発表日 2008年09月16日 - On a special class of primitive words
Elena Czeizler
口頭発表（一般）, 英語, MFCS2008: 33rd International Symposium on Mathematical Foundations of Computer Science, Torun, Poland, 国際会議
発表日 2008年08月27日 - Towards the sequence design preventing pseudoknot formation
関 新之助
口頭発表（一般）, 英語, IWNC2007: 2nd International Workshop on Natural Computing, Nagoya, Japan, 国際会議
発表日 2007年12月10日 - An efficient multiple alignment method for DNA secondary structures including pseudoknots
関 新之助
口頭発表（一般）, 英語, IWNC2007: 2nd International Workshop on Natural Computing, Nagoya, Japan, 国際会議
発表日 2007年12月10日 - Hierarchical alignment of RNA secondary structures including pseudoknots
関 新之助
ポスター発表, 英語, GIW2004: 15th International Workshop on Genome Informatics, Yokohama, Japan, 国際会議
発表日 2004年12月13日 - Efficient learning of k-reversible context-free grammars from positive structural examples
関 新之助
ポスター発表, 英語, ICGI: 7th International Colloquium on Grammatical Inferences, Athens, Greece, 国際会議
発表日 2004年10月11日
担当経験のある科目_授業
共同研究・競争的資金等の研究課題
- 文字列の辞書式順序の組合せ論とその応用
坂内 英夫
研究期間 2020年04月01日 - 2024年03月31日 - 共転写性フォールディングの本質的計算完全性
研究期間 2020年04月01日 - 2023年03月31日 - 万能折り畳みシステムの小型化とその限界
研究期間 2018年06月29日 - 2020年03月31日 - 国際会議UCNC2019への助成
Shinnosuke Seki
立石科学技術振興財団
研究期間 2018年09月25日 - 2019年06月07日 - 国際会議DLT2018への助成
関 新之助
情報通信研究機構, Support for the 22nd International Conference on Developments in Language Theory (DLT 2018), 研究代表者
研究期間 2018年04月01日 - 共転写性フォールディングによる自己組織化システムの実際的設計と最適化
研究期間 2016年04月01日 - 2018年03月31日 - 国際会議DLT2018への助成
Shinnosuke Seki
電気通信普及財団, シンポジウム・セミナー 振興普及援助
研究期間 2017年09月01日 - 機関選抜のため、研究テーマはなし
関 新之助
科学技術振興機構, 研究代表者
研究期間 2015年08月06日 - 2017年03月31日 - 国際会議DLT2018への助成
（株）久保田情報技研, 国際会議DLT2018開催支援寄付金
研究期間 2017年 - 共転写性フォールディングの数理モデル化とチューリング完全性
関 新之助
研究代表者
研究期間 2015年04月01日 - 2016年03月31日 - 分子自己組織化システムの実際的な設計とその最適化
関 新之助
Academy of Finland, 研究代表者
研究期間 2013年09月01日 - 2015年03月31日