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, FI00076 Aalto, Finland
 Telephone:
 +358 9 470 23366
 Email:
 firstname.lastname@aalto.fi
News
Courses (Fall 2014)
Research interests
 Algorithmic selfassembly
 Automata theory
 Combinatorics
Editorial Board
Grants
Academy of Finland Postdoctoral Researcher Grants (Grant No. 13266670/T30606, September 1st, 2013 )
I am the PI (principle investigator) of the 3year research project titled "Practical designs of molecular selfassembly systems and their optimization" awareded by the Research Council for Natural Sciences and Engineering of the Academy of Finland.
Conference Organizations
 NCMA 2015: 7th International Workshop on NonClassical Models of Automata and Applications, Porto, Portugal, August 31September 1, 2015. (PC member)
 DNA 20: 20th DNA Computing and Molecular Programming, Kyoto, Japan, September 2226, 2014. (PC member)
 DNA 19: 19th DNA Computing and Molecular Programming, Tempe, Arizona, USA, September 2227, 2013. (PC member)
 DLT 2010: 14th International Conference on Developments in Language Theory, London, Ontario, Canada, August 1720, 2010.
DNA WatsonCrick 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 4year 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

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 1720.
Lecture Notes in Computer Science, vol. 6224, Springer, 2010.
See Springer's website
Invited refereed book chapters
2012

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, 10731127, Springer (2012).
PDF.
See Springer's website
Refereed journal papers
2014

O. H. Ibarra and S. Seki.
Semilinear sets and counter machines: a brief survey.
Fundamenta Informaticae, to appear.

L. Kari, S. Kopecki, and S. Seki.
3color bounded patterned selfassembly.
Natural Computing, to appear.

HL. Chen, D. Doty, and S. Seki.
Program size and temperature in selfassembly.
Algorithmica, doi 10.1007/s0045301498793, to appear.

R. Lemoy, A. Mozeika, and S. Seki.
Transfer matrix analysis of onedimensional majority cellular automata with thermal noise.
Journal of Physics A: Mathematical and Theoretical 47 105001, doi:10.1088/17518113/47/10/105001. Article in Press
2013

O. H. Ibarra and S. Seki.
On the open problem of Ginsburg concerning semilinear sets and related problems.
Theoretical Computer Science 501, (2013) 1119. Article in Press

G. J. Lavado, G. Pighizzini, and S. Seki.
Converting nondeterministic automata and contextfree grammars into Parikh equivalent oneway and twoway deterministic automata.
Information and Computation 228229, (2013) 115. Article in Press, arXiv

S. Seki and Y. Okuno.
On the behavior of tile assembly model at high temperatures.
Computability 2(2), (2013) 107124.

N. Bryans, E. Chiniforooshan, D. Doty, L. Kari, and S. Seki.
The power of nondeterminism in selfassembly.
Theory of Computing 9, (2013) 129.

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) 589603.
Article in press,
PDF.
2012

O. H. Ibarra and S. Seki.
Characterizations of bounded semilinear languages by oneway and twoway deterministic machines.
International Journal of Foundations of Computer Science 23(6) (2012), 12911305. Article in Press

E. Chiniforooshan, M. Daley, O. H. Ibarra, L. Kari, and S. Seki.
Onereversal counter machines and multihead automata: revisited.
Theoretical Computer Science 454 (2012), 8187. Article in Press.

S. Seki.
Absoluteness of subword inequality is undecidable.
Theoretical Computer Science 418 (2012) 116120.
Article in Press, PDF, PS, arXiv.
2011

L. Kari, S. Kopecki, and S. Seki.
On the regularity of iterated hairpin completion of a single word.
Fundamenta Informaticae 110(14) (2011) 201215.
PDF, PS, arXiv

L. Kari and S. Seki.
Schema for parallel insertion and deletion: revisited.
International Journal of Foundations of Computer Science 22(7) (2011) 16551668.
Article in Press.

E. Czeizler, E. Czeizler, L. Kari, and S. Seki.
An extension of the Lyndon Schutzenberger result to pseudoperiodic words.
Information and Computation 209 (2011) 717730.
Article in Press.

L. Kari, B. Masson, and S. Seki.
Properties of pseudoprimitive words and their applications.
International Journal of Foundations of Computer Science 22(2) (2011) 447471.
HAL archives (PDF and PS), Article in Press.

B. Cui, L. Kari, and S. Seki.
Kcomma codes and their generalizations.
Fundamenta Informaticae 107 (2011) 118.
Abstract on the publisher's site.

M. Daley, L. Kari, S. Seki, and P. Sosik.
Orthogonal shuffle on trajectories.
International Journal of Foundations of Computer Science, 22(1) (2011) 213222.

B. Cui, L. Kari, and S. Seki.
Block insertion and deletion on trajectories.
Theoretical Computer Science, 412(810) (2011) 714728.
Article in Press.
2010

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) 215236.
PDF, PS.

E. Czeizler, L. Kari, and S. Seki.
On a special class of primitive words.
Theoretical Computer Science 411(3) (2010) 617630.
Article in Press.
2009

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) 4361.
Article in Press.

L. Kari and S. Seki.
On pseudoknotbordered words and their properties.
Journal of Computer and System Sciences 75 (2009) 113121.
Article in Press.

L. Kari, K. Mahalingam, and S. Seki.
Twinroots of words and their properties.
Theoretical Computer Science 410 (2009) 23932400.
Article in Press.
2005

S. Seki and S. Kobayashi.
A grammatical approach to the alignment of structureannotated strings.
IEICE Transactions on Information and Systems: E88D(12) (2005) 27272737.
Conferences and presentations
2014

F. Manea, M. Müller, D. Nowotka, and S. Seki.
Generalized LyndonSchützenberger equations.
MFCS 2014:
Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (Budapest, Hungary, August 2529, 2014), LNCS 8634, Springer, 402413, 2014.

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 58, 2014), LNCS 8614, Springer, 294305, 2014.
Slides (PDF).

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 2530, 2014), LNCS 8327, Springer, 339350, 2014. Slide (PDF)
2013

A. Johnsen, MY. Kao, and S. Seki.
Computing minimum tile sets to selfassemble color patterns.
ISAAC 2013:
Proceedings of the 24th International Symposium on Algorithms and Computation (Hong Kong, China, December 1618, 2013), LNCS 8283, Springer, 699710, 2013.

L. Kari, S. Kopecki, and S. Seki.
3color bounded patterned selfassembly.
DNA 19:
Proceedings of the 19th International Conference on DNA Computing and Molecular Programming (Tempe, Arizona, USA, September 2227, 2013), LNCS 8141, Springer, 105117, 2013.

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 15, 2013), LNCS 7956, Springer, 220231, 2013. Presentation slide (PDF), Figures (in color)

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 2022, 2013), LNCS 7876, Springer, 156168, 2013.
2012

G. Lavado, G. Pighizzini, and S. Seki.
Converting nondeterministic automata and contextfree grammars into Parikh equivalent deterministic automata.
ICTCS 2012:
Proceedings of the 13th Italian Conference on Theoretical Computer Science (Varese, Italy, September 1921, 2012), to appear.

G. Lavado, G. Pighizzini, and S. Seki.
Converting nondeterministic automata and contextfree grammars into Parikh equivalent deterministic automata.
DLT 2012:
Proceedings of the 16th International Conference on Developments in Language Theory (Taipei, Taiwan, August 1417, 2012), LNCS 7410, Springer, 284295, 2012.

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 1823, 2012), LNCS 7318, Springer, 549559, 2012. Presentation (PDF), arXiv

L. Kari, S. Seki, and Z. Xu.
Triangular and hexagonal tile selfassembly 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 2124, 2012), LNCS 7160, Springer, 357375, 2012.

L. Kari, S. Kopecki, and S. Seki.
Iterated hairpin completions of noncrossing words.
SOFSEM 2012:
Proceedings of the 38th International Conference on Current Trends in Theory and Practice of Computer Science (Spindleruv Mlyn, Czech Republic, January 2127, 2012), LNCS 7174, Springer, 337348, 2012.
PDF. arXiv
2011

HL. Chen, D. Doty, and S. Seki.
Program size and temperature in selfassembly.
ISAAC 2011:
Proceedings of the The 22nd International Symposium on Algorithms and Computation (Yokohama, Japan, December 58, 2011).
LNCS 7074, Springer, 445453, 2011.
arXiv.

O. H. Ibarra and S. Seki.
Characterizations of bounded semilinear languages by oneway and twoway deterministic machines.
AFL 2011:
Proceedings of the 13th International Conference on Automata and Formal Languages (Debrecen, Hungary, August 1722, 2011), 211224, 2011.
Slides (PDF), (powerpoint).

E. Chiniforooshan, M. Daley, O. H. Ibarra, L. Kari, and S. Seki.
Onereversal 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. 2228, 2011),
LNCS 6543, Springer, 166177, 2011.
Article in Press, Slides (PDF).

N. Bryans, E. Chiniforooshan, D. Doty, L. Kari, and S. Seki.
The power of nondeterminism in selfassembly.
SODA 2011:
Proceedings of ACMSIAM Symposium on Discrete Algorithms (San Francisco, California, USA, January 2325, 2011), 590602, 2011.
PDF.
2010

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 1720, 2010),
LNCS 6224, Springer, 267278, 2010.
PDF,
PS,
Slides (PDF).

E. Chiniforooshan, D. Doty, L. Kari, and S. Seki.
Scalable, timeresponsive, digital, energyefficient, molecular circuits using DNA strand displacement.
DNA 16:
Proceedings of the 16th International Conference on DNA Computing and Molecular Programming (HongKong, China, June 1417th, 2010).
LNCS 6518, Springer, 2536, 2011.
Article in Press, arXiv.

L. Kari, S. Seki, and Z. Xu.
Triangular tile selfassembly systems.
DNA 16:
Proceedings of the 16th International Conference on DNA Computing and Molecular Programming (HongKong, China, June 1417th, 2010).
LNCS 6518, Springer, 8999, 2011.
2009

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 30July 3, 2009),
LNCS 5583, Springer, 183194, 2009.
Slides (PDF)

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 1922, 2009),
LNCS 5725, Springer, 204219, 2009.
2008

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 1619, 2008),
LNCS 5257, Springer, 419430, 2008.

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 2529, 2008),
LNCS 5162, Springer, 265277, 2008.
2007

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 1012, 2007),
PICT1, Springer, 101110, 2009.

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 1012, 2007),
PICT1, Springer, 179188, 2009.
2005

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) 339340.
2004

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 (GIW2004) (2004) 1171  1172.

S. Seki and S. Kobayashi.
Efficient learning of kreversible contextfree 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) 285287.