(aside image)

Shinnosuke Seki

Ph.D., Academy of Finland, Postdoctoral Researcher

Office:
Room B246 in Computer Science Building,
Konemiehentie 2, Otaniemi campus area, Espoo, Finland.
Postal Address:
Aalto University, School of Science,
Department of Information and Computer Science,
P.O. Box 15400, FI-00076 Aalto, Finland
Telephone:
+358 9 470 23366
Email:
firstname.lastname@aalto.fi

News

Courses (Fall 2014)

Research interests

Editorial Board

Grants

Academy of Finland Postdoctoral Researcher Grants (Grant No. 13266670/T30606, September 1st, 2013 -)

I am the PI (principle investigator) of the 3-year research project titled "Practical designs of molecular self-assembly systems and their optimization" awareded by the Research Council for Natural Sciences and Engineering of the Academy of Finland.

Conference Organizations

DNA Watson-Crick complementarity in computer science

This is my Ph.D. thesis, which is a collection of my works done mainly in the first 2 years (September 2006 - August 2008) of my 4-year career as a Ph.D. candidate under the supervision of Professor Dr. Lila Kari at the Department of Computer Science, University of Western Ontario in Canada. This thesis was successfully defended on August 9th (Mon), 2010.
PDF, PS, Slides (PDF)

Publications

Editorial Works

2010

  1. Y. Gao, H. Lu, S. Seki, and S. Yu (Eds.). Proceedings of 14th International Conference on Developments in Language Theory (DLT 2010), London, Ontario, Canada, August 17-20. Lecture Notes in Computer Science, vol. 6224, Springer, 2010. See Springer's website

    2. Invited refereed book chapters

    2012

    1. L. Kari, S. Seki, and P. Sosik. DNA Computing: Foundations and Implications. In: G. Rozenberg, T. Bäck, and J. N. Kok (Eds.) Handbook of Natural Computing, 1073-1127, Springer (2012). PDF. See Springer's website

      2. Refereed journal papers

      2014

      1. O. H. Ibarra and S. Seki. Semilinear sets and counter machines: a brief survey. Fundamenta Informaticae, to appear.
      2. L. Kari, S. Kopecki, and S. Seki. 3-color bounded patterned self-assembly. Natural Computing, to appear.
      3. H-L. Chen, D. Doty, and S. Seki. Program size and temperature in self-assembly. Algorithmica, doi 10.1007/s00453-014-9879-3, to appear.
      4. R. Lemoy, A. Mozeika, and S. Seki. Transfer matrix analysis of one-dimensional majority cellular automata with thermal noise. Journal of Physics A: Mathematical and Theoretical 47 105001, doi:10.1088/1751-8113/47/10/105001. Article in Press

      2013

      1. O. H. Ibarra and S. Seki. On the open problem of Ginsburg concerning semilinear sets and related problems. Theoretical Computer Science 501, (2013) 11-19. Article in Press
      2. G. J. Lavado, G. Pighizzini, and S. Seki. Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata. Information and Computation 228-229, (2013) 1-15. Article in Press, arXiv
      3. S. Seki and Y. Okuno. On the behavior of tile assembly model at high temperatures. Computability 2(2), (2013) 107-124.
      4. N. Bryans, E. Chiniforooshan, D. Doty, L. Kari, and S. Seki. The power of nondeterminism in self-assembly. Theory of Computing 9, (2013) 1-29.
      5. S. Z. Fazekas, H. Ito, Y. Okuno, S. Seki, and K. Taneishi. On computational complexity of graph inference from counting. Natural Computing 12(4), (2013) 589-603. Article in press, PDF.

      2012

      1. O. H. Ibarra and S. Seki. Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. International Journal of Foundations of Computer Science 23(6) (2012), 1291-1305. Article in Press
      2. E. Chiniforooshan, M. Daley, O. H. Ibarra, L. Kari, and S. Seki. One-reversal counter machines and multihead automata: revisited. Theoretical Computer Science 454 (2012), 81-87. Article in Press.
      3. S. Seki. Absoluteness of subword inequality is undecidable. Theoretical Computer Science 418 (2012) 116-120. Article in Press, PDF, PS, arXiv.

      2011

      1. L. Kari, S. Kopecki, and S. Seki. On the regularity of iterated hairpin completion of a single word. Fundamenta Informaticae 110(1-4) (2011) 201-215. PDF, PS, arXiv
      2. L. Kari and S. Seki. Schema for parallel insertion and deletion: revisited. International Journal of Foundations of Computer Science 22(7) (2011) 1655-1668. Article in Press.
      3. E. Czeizler, E. Czeizler, L. Kari, and S. Seki. An extension of the Lyndon Schutzenberger result to pseudoperiodic words. Information and Computation 209 (2011) 717-730. Article in Press.
      4. L. Kari, B. Masson, and S. Seki. Properties of pseudo-primitive words and their applications. International Journal of Foundations of Computer Science 22(2) (2011) 447-471. HAL archives (PDF and PS), Article in Press.
      5. B. Cui, L. Kari, and S. Seki. K-comma codes and their generalizations. Fundamenta Informaticae 107 (2011) 1-18. Abstract on the publisher's site.
      6. M. Daley, L. Kari, S. Seki, and P. Sosik. Orthogonal shuffle on trajectories. International Journal of Foundations of Computer Science, 22(1) (2011) 213-222.
      7. B. Cui, L. Kari, and S. Seki. Block insertion and deletion on trajectories. Theoretical Computer Science, 412(8-10) (2011) 714-728. Article in Press.

      2010

      1. L. Kari and S. Seki. An improved bound for an extension of Fine and Wilf's theorem and its optimality. Fundamenta Informaticae 101(3) (2010) 215-236. PDF, PS.
      2. E. Czeizler, L. Kari, and S. Seki. On a special class of primitive words. Theoretical Computer Science 411(3) (2010) 617-630. Article in Press.

      2009

      1. M. Ito, L. Kari, Z. Kincaid, and S. Seki. Duplication in DNA sequences. In: A. Condon, D. Harel, J. N. Kok, A. Salomaa, E. Winfree (Eds.) Algorithmic Bioprocesses, Natural Computing Series, Springer (2009) 43-61. Article in Press.
      2. L. Kari and S. Seki. On pseudoknot-bordered words and their properties. Journal of Computer and System Sciences 75 (2009) 113-121. Article in Press.
      3. L. Kari, K. Mahalingam, and S. Seki. Twin-roots of words and their properties. Theoretical Computer Science 410 (2009) 2393-2400. Article in Press.

      2005

      1. S. Seki and S. Kobayashi. A grammatical approach to the alignment of structure-annotated strings. IEICE Transactions on Information and Systems: E88-D(12) (2005) 2727-2737.

      Conferences and presentations

      2014

      1. F. Manea, M. Müller, D. Nowotka, and S. Seki. Generalized Lyndon-Schützenberger equations. MFCS 2014: Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (Budapest, Hungary, August 25-29, 2014), LNCS 8634, Springer, 402-413, 2014.
      2. G. J. Lavado, G. Pighizzini, and S. Seki. Operational state complexity under Parikh equivalence. DCFS 2014: Proceedings of the 16th International Workshop on Descriptional Complexity of Formal Systems (Turku, Finland, August 5-8, 2014), LNCS 8614, Springer, 294-305, 2014. Slides (PDF).
      3. N. Jonoska, F. Manea, and S. Seki. Stronger square conjecture on binary words. SOFSEM 2014: Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (High Tatras, Slovakia, January 25-30, 2014), LNCS 8327, Springer, 339-350, 2014. Slide (PDF)

      2013

      1. A. Johnsen, M-Y. Kao, and S. Seki. Computing minimum tile sets to self-assemble color patterns. ISAAC 2013: Proceedings of the 24th International Symposium on Algorithms and Computation (Hong Kong, China, December 16-18, 2013), LNCS 8283, Springer, 699-710, 2013.
      2. L. Kari, S. Kopecki, and S. Seki. 3-color bounded patterned self-assembly. DNA 19: Proceedings of the 19th International Conference on DNA Computing and Molecular Programming (Tempe, Arizona, USA, September 22-27, 2013), LNCS 8141, Springer, 105-117, 2013.
      3. S. Seki. Combinatorial optimization in pattern assembly (extended abstract). UCNC 2013: Proceedings of the Unconventional Computational and Natural Computation - 12th International Conference (Milan, Italy, July 1-5, 2013), LNCS 7956, Springer, 220-231, 2013. Presentation slide (PDF), Figures (in color)
      4. O. H. Ibarra and S. Seki. On the boundedness property of semilinear sets. TAMC 2013: Proceedings of the 10th annual conference on Theory and Applications of Models of Computation (Hong Kong, China, May 20-22, 2013), LNCS 7876, Springer, 156-168, 2013.

      2012

      1. G. Lavado, G. Pighizzini, and S. Seki. Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata. ICTCS 2012: Proceedings of the 13th Italian Conference on Theoretical Computer Science (Varese, Italy, September 19-21, 2012), to appear.
      2. G. Lavado, G. Pighizzini, and S. Seki. Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata. DLT 2012: Proceedings of the 16th International Conference on Developments in Language Theory (Taipei, Taiwan, August 14-17, 2012), LNCS 7410, Springer, 284-295, 2012.
      3. S. Seki and Y. Okuno. On the behavior of tile assembly system at high temperatures. CiE 2012: Proceedings of the Turing Centenary Conference - How the World Computes (Cambridge, United Kingdom, June 18-23, 2012), LNCS 7318, Springer, 549-559, 2012. Presentation (PDF), arXiv
      4. L. Kari, S. Seki, and Z. Xu. Triangular and hexagonal tile self-assembly systems. WTCS 2012: Proceedings of the International Workshop on Theoretical Computer Science: Dedicated to Professor Christian S. Calude's 60th Birthday (Auckland, New Zealand, February 21-24, 2012), LNCS 7160, Springer, 357-375, 2012.
      5. L. Kari, S. Kopecki, and S. Seki. Iterated hairpin completions of non-crossing words. SOFSEM 2012: Proceedings of the 38th International Conference on Current Trends in Theory and Practice of Computer Science (Spindleruv Mlyn, Czech Republic, January 21-27, 2012), LNCS 7174, Springer, 337-348, 2012. PDF. arXiv

      2011

      1. H-L. Chen, D. Doty, and S. Seki. Program size and temperature in self-assembly. ISAAC 2011: Proceedings of the The 22nd International Symposium on Algorithms and Computation (Yokohama, Japan, December 5-8, 2011). LNCS 7074, Springer, 445-453, 2011. arXiv.
      2. O. H. Ibarra and S. Seki. Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. AFL 2011: Proceedings of the 13th International Conference on Automata and Formal Languages (Debrecen, Hungary, August 17-22, 2011), 211-224, 2011. Slides (PDF), (powerpoint).
      3. E. Chiniforooshan, M. Daley, O. H. Ibarra, L. Kari, and S. Seki. One-reversal counter machines and multihead automata: revisited. SOFSEM 2011: Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (Novy Smokovec, Slovakia, Jan. 22-28, 2011), LNCS 6543, Springer, 166-177, 2011. Article in Press, Slides (PDF).
      4. N. Bryans, E. Chiniforooshan, D. Doty, L. Kari, and S. Seki. The power of nondeterminism in self-assembly. SODA 2011: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, USA, January 23-25, 2011), 590-602, 2011. PDF.

      2010

      1. L. Kari and S. Seki. Schema for parallel insertion and deletion. DLT 2010: Proceedings of 14th International Conference on Developments in Language Theory (London, Canada, August 17-20, 2010), LNCS 6224, Springer, 267-278, 2010. PDF, PS, Slides (PDF).
      2. E. Chiniforooshan, D. Doty, L. Kari, and S. Seki. Scalable, time-responsive, digital, energy-efficient, molecular circuits using DNA strand displacement. DNA 16: Proceedings of the 16th International Conference on DNA Computing and Molecular Programming (HongKong, China, June 14-17th, 2010). LNCS 6518, Springer, 25-36, 2011. Article in Press, arXiv.
      3. L. Kari, S. Seki, and Z. Xu. Triangular tile self-assembly systems. DNA 16: Proceedings of the 16th International Conference on DNA Computing and Molecular Programming (HongKong, China, June 14-17th, 2010). LNCS 6518, Springer, 89-99, 2011.

      2009

      1. E. Czeizler, E. Czeizler, L. Kari, and S. Seki. An extension of the Lyndon Schutzenberger result to pseudoperiodic words. DLT 2009: Proceedings of the 13th International Conference on Developments in Language Theory (Stuttgart, Germany, June 30-July 3, 2009), LNCS 5583, Springer, 183-194, 2009. Slides (PDF)
      2. B. Cui, L. Kari, and S. Seki. On the reversibility of parallel insertion, and its relation to comma codes. CAI 2009: Proceedings of the 3rd International Conference on Algebraic Informatics (Thessaloniki, Greece, May 19-22, 2009), LNCS 5725, Springer, 204-219, 2009.

      2008

      1. M. Ito, L. Kari, Z. Kincaid, and S. Seki. Duplication in DNA sequences. DLT 2008: Proceedings of the Developments in Language Theory (Kyoto, Japan, September 16-19, 2008), LNCS 5257, Springer, 419-430, 2008.
      2. E. Czeizler, L. Kari, and S. Seki. On a special class of primitive words. MFCS 2008: Proceedings of the Mathematical Foundations of Computer Science (Torun, Poland, August 25-29, 2008), LNCS 5162, Springer, 265-277, 2008.

      2007

      1. L. Kari and S. Seki. Towards the sequence design preventing pseudoknot formation. IWNC 2007: Proceedings of the 2nd International Workshop on Natural Computing (Nagoya, Japan, December 10-12, 2007), PICT1, Springer, 101-110, 2009.
      2. S. Kobayashi and S. Seki. An efficient multiple alignment method for RNA secondary structures including pseudoknots. IWNC 2007: Proceedings of the 2nd International Workshop on Natural Computing (Nagoya, Japan, December 10-12, 2007), PICT1, Springer, 179-188, 2009.

      2005

      1. T. Takakura, H. Asakawa, S. Seki, and S. Kobayashi. Efficient tree grammatical modeling of RNA secondary structures from alignment data. Poster abstracts of Recomb2005 (2005) 339-340.

      2004

      1. S. Seki, A. Kijima, S. Kobayashi, and G. Sanpei. Hierarchical alignment of RNA secondary structures including pseudoknots. In: Proc. 15th International Conference on Genome Informatics (GIW-2004) (2004) 117-1 - 117-2.
      2. S. Seki and S. Kobayashi. Efficient learning of k-reversible context-free grammars from positive structural examples. ICGI 2004: Proceedings of the 7th International Colloquium on Grammatical Inference (Athens, Greece, October 11 - 13, 2004), LNAI 3264, Springer (2004) 285-287.