Fundamentals of Computing and Discrete Mathematics

Selected Publications

Books

  1. Gérard Cohen, Iiro Honkala, Simon Litsyn and Antoine Lobstein: Covering Codes. Elsevier. xxii + 542 pages, North-Holland Mathematical Library 54, 1997.
  2. Andrzej Ehrenfeucht, Tero Harju and Grzegorz Rozenberg: The Theory of 2-Structures. A framework for decomposition and transformation of graphs. World Scientific, 1999.
  3. Mika Hirvensalo: Quantum Computing, a monograph, xiii+214 pp. (2nd edition). Springer Series on Natural Computing (2004).
  4. Andrzej Ehrenfeucht, Tero Harju, Ion Petre, D.M. Prescott and Grzegorz Rozenberg: Computation in Living Cell. Springer-Verlag. xviii + 201 pages, 2004.
  5. Cusick, T., Ding, C., & Renvall, A.: Stream Ciphers and Number Theory, Revised Edition. Elsevier B.V., 2004.

Edited Books

  1. Wilfried Brauer, Hartmut Ehrig, Juhani Karhumäki, Arto Salomaa, editors. Formal and Natural Computing - Essays Dedicated to Grzegorz Rozenberg on the occasion of his 60th birthday, LNCS 2300, Springer, 2002.
  2. Juhani Karhumäki, Hermann Maurer, Gheorge Paun, Grzegorz Rozenberg, editors. Theory is forever, Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday, LNCS 3113, Springer, Berlin, 2004.
  3. Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Don Sannella, editors. Proceedings of the 31st International Colloquium on Automata, Languages and Programming, volume 3142 of Lecture Notes in Computer Science, Berlin, 2004. Springer.
  4. Alberto Bertoni, Zoltan Esik, Juhani Karhumäki, guest editors. Special issue dedicated to the 60th birthday of Christian Choffrut, Theoretical Computer Science 330(1-2), 2006.
  5. Anssi Yli-Jyrä, Lauri Karttunen, Juhani Karhumäki, editors. Finite State Methods in Natural Language Processing, Proceedings of FSMNLP 2005, LNCS 4002, Springer, 2006.
  6. Tero Harju, Juhani Karhumäki, Arto Lepistö, editors. Proceedings of the 11th Developments in Language Theory, volume 4588 of Lecture Notes in Computer Science, Berlin 2007. Springer.
  7. Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Mária Bieliková, Pavol Návrat, editors. SOFSEM 2008: Theory and Practice of Computer Science, Proceedings of SOFSEM 2008, LNCS 4910, Springer, 2008.
  8. Jarkko Kari, area editor for Cellular Automata. G. Rozenberg, T. Bäck, J.N. Kok, editors. Handbook of Natural computing. Springer, to appear.
  9. Mika Hirvensalo, area editor for Quantum Computation. G. Rozenberg, T. Bäck, J.N. Kok, editors. Handbook of Natural computing. Springer, 2010.
  10. Proceedings of the 7th International Computer Science Symposium in Russian
  11. C.S. Calude, J. Kari, I. Petre, G. Rozenberg, editors. Proceedings of Unconventional Computation 2011. Lecture Notes in Computer Science, volume 6714, Springer, 2011.

Special Issues of Journals

  1. Jarkko Kari (guest editor). Special issue on theoretical aspects of cellular cutomata. Theor. Comput. Sci. 325(2):169-344, 2004.
  2. Jean Berstel, Juhani Karhumäki, and Dominique Perrin (guest editors). Special issue on combinatorics on words with applications. International Journal of Foundations of Computer Science, 15:223-383, 2004.
  3. Tero Harju, Juhani Karhumäki, and Antonio Restivo (guest editors). Special issue of WORDS'03. Theor. Comput. Sci. 339:1-165, 2005.
  4. Juhani Karhumäki and Grzegorz Rozenberg (guest editors). Special issue dedicated to the 70th birthday of Arto Salomaa. Theoret. Comput. Sci., 330:1-191, 2005.
  5. Josep Díaz and Juhani Karhumäki (guest editors). Special issue of selected papers of ICALP'04. Theoret. Comput. Sci., 348(2-3): 129-366, 2006.
  6. Tero Harju and Juhani Karhumäki (guest editors). Special issue of DLT'07. Internat. J. Found. Comput. Sci. 19(3) 495-690, 2008.
  7. Jean Berstel, Tero Harju, and Juhani Karhumäki (guest editors). Special issue of the Workshop on the Fibonacci Words. RAIRO, Theoretical Informatics and Applications 42(4) 657-762, 2008.
  8. Natasa Jonoska and Jarkko Kari (guest editors). Special issue on Aspects of Molecular Self-Assembly. Theor. Comput. Sci. 410(15), 2009.
  9. Natasa Jonoska and Jarkko Kari (guest editors). Special issue on Theory and Applications of Tilings. Theor. Comput. Sci. 410(16), 2009.
  10. Tero Harju, Alexander Okhotin, Grzegorz Rozenberg and Arto Salomaa (guest editors). "A bird's eye view of theory" Special issue in honour of Juhani Karhumäki. Theoret. Comput. Sci. 410 (30-32), 2009.
  11. Mika Hirvensalo (guest editor): "Quantum And Probabilistic Automata", Special issue of Theoretical Computer Science 410:20, May 2009
  12. Henning Bordihn, Mika Hirvensalo, Martin Kutrib, Rudolf Freund, Markus Holzer, Freidrich Otto (guest editors). Non-Classical Models of Automata and Applications, Special issue of Fundamenta Informaticae 104:1-2, 2010.
  13. Juhani Karhumäki, Gheorghe Paun, Grzegorz Rozenberg and Arto Salomaa (guest editors). Special issue dedicated to Oscar Ibarra. Fundamenta Informaticae 110:1-4, 2011.
  14. Giorgio Ausiello, Hendrik Jan Hoogeboom, Juhani Karhumäki, Ion Petre and Arto Salomaa (guest editors). Special issue dedicated to Grzegorz Rozenberg. Theoretical Computer Science 429, 2012.
  15. Juhani Karhumäki and Edward Hirsch (guest editors). Special issue of the 7th International Computer Science Symposium in Russia. Theory of Computing Systems, to appear.
  16. J. Kari, editor. Cellular Automata and Discrete Complex Systems. Theoretical Computer Science 412(30), 2011.

Chapters in Handbooks

  1. Christian Choffrut and Juhani Karhumäki. Combinatorics of words. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of formal languages, Vol. 1, pages 329-438. Springer, Berlin, 1997.
  2. Karel Culik and Jarkko Kari. Digital Images and Formal languages. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of formal languages, Vol. 3, pages 599-616. Springer, Berlin, 1997.
  3. Tero Harju and Juhani Karhumäki. Morphisms. In Grzegorz Rozenberg and Arto Salomaa, editors. Handbook of formal languages, Vol. 1, pages 439-510. Springer, Berlin, 1997.
  4. Iiro Honkala and Aimo Tietäväinen: Codes and number theory. Invited chapter in it Handbook of Coding Theory, (eds. V. S. Pless and W. C. Huffman), 1998, pp. 1141-1194.
  5. Juhani Karhumäki: D0L Sequences. In: The Kluwer Encyclopaedia of Mathematics, 141-142. Kluwer, Dordrecht, 2000.
  6. Tero Harju, Juhani Karhumäki and Wojciech Plandowski. Independent systems of equations. In Dominique Perrin and Jean Berstel, editors, M. Lothaire: Algebraic combinatorics on words, pages 443-472. Cambridge University Press, Cambridge, 2002.
  7. J. Albert and Jarkko Kari. Digital Image Compression. In M. Droste, W. Kuich, H. Vogler, editors. Handbook of Weighted Automata, pages 453-479. Springer, 2009.
  8. Jarkko Kari. Tiling Problem and Undecidability in Cellular Automata. In R.A. Meyers, editor. Encyclopedia of Complexity and Systems Science, pages 9158-9172. Springer, 2009.
  9. Jarkko Kari. Data Compression Codes, Lossy. In Benjamin W. Wah, editor. Wiley Encyclopedia of Computer Science and Engineering, Volume 2, pages 793-804. John Wiley & Sons, 2009.
  10. Juha Honkala. Lindenmayer Systems. In M. Droste, W. Kuich, H. Vogler, editors. Handbook of Weighted Automata. pages 291-311. Springer, 2009.
  11. Tero Harju and Juhani Karhumäki. Finite Transducers and Rational Transductions. In Jean-Éric Pin, editor. Handbook of Automata. To appear.
  12. Jarkko Kari and M. Volkov. Cerny's conjecture and the road coloring problem. In Jean-Éric Pin, editor. Handbook of Automata. To appear.
  13. Mika Hirvensalo: Mathematics for Quantum Information Processing. In G. Rozenberg, T. Bäck, J. Kok (eds.): Handbook of Natural Computing (Springer 2010).
  14. Robert Brijder, Mark Daley, Tero Harju, Natasha Jonoska, Ion Petre and Grzegorz Rozenberg. Computational gene assembly in ciliates. In G. Rozenberg, T. Bäck, J. Kok (eds.): Handbook of Natural Computing (Springer-Verlag 2010).
  15. Juha Honkala: Lindenmayer systems. Chapter 8 in M. Droste, W. Kuich and H. Vogler (eds.): Handbook of Weighted Automata, Springer 2009, pp. 291-311.
  16. Juha Honkala: The equality problem for purely substitutive words. Chapter 10 in V. Berthe and M. Rigo (eds.): Combinatorics, Automata and Number Theory, Cambridge University Press 2010, pp. 505-529.
  17. Tero Harju, Juhani Karhumäki: Finite transducers and rational transduction. a chapter in Handbook of Automata. European Mathematical Society (to appear)
  18. Juhani Karhumäki, Jarkko Kari: Finite automata and image manipulation. a chapter in Handbook of Automata. European Mathematical Society (to appear)
  19. J.Kari. Basic Concepts of Cellular Automata. In: G. Rozenberg, T. Bäck, J. Kok, editors: Handbook of Natural Computing. Springer, to appear.
  20. J. Kari, V. Salo. A Survey on Picture-Walking Automata. In: W. Kuich and G. Rahonis, editors: Algebraic Foundations in Computer Science - Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement. Lecture Notes in Computer Science 7020, Springer, pp. 183-213, 2011.

Fundamental papers

  1. Tero Harju and Juhani Karhumäki. The equivalence problem of multitape finite automata. Theoret. Comput. Sci., 78:347-355, 1991.
  2. Karel Culik and Tero Harju. Splicing semigroups of dominoes and DNA. Discrete Applied Math. 31 261-277, 1991.
  3. Karel Culik, Jarkko Kari. Image Compression Using Weighted Finite Automata. Computers and Graphics 17, 305-313, 1993.
  4. Jarkko Kari. Reversibility and surjectivity problems of Cellular automata. Journal of Computer and System Sciences 48, 149-182, 1994.
  5. Karel Culik II and Juhani Karhumäki. Finite automata computing real functions. SIAM J. Comput., 23(4):789-814, 1994.
  6. Jarkko Kari. A small aperiodic set of Wang tiles. Discrete Mathematics 160, 259-264, 1996.
  7. Vesa Halava, Tero Harju and Mika Hirvensalo. Generalized Post Correspondence Problem for marked morphism. Internat. J. Algebra Comput. 10 (2000), 757 - 772.
  8. Juhani Karhumäki, Filippo Mignosi and Wojciech Plandowski. The expressibility of languages and relations by word equations. J. ACM, 47(3):483-505, 2000.
  9. Juhani Karhumäki, Arto Lepistö and Wojciech Plandowski. Locally periodic versus globally periodic infinite words. J. Comb. Theory, Ser. A, 100(2):250-264, 2002
  10. Christian Choffrut, Juhani Karhumäki and Nicolas Ollinger. The commutation of finite sets: a challenging problem. Theoretical Computer Science, 273(1-2):69-79, 2002
  11. Karel Culik, Juhani Karhumäki and Jarkko Kari. A note on synchronized automata and road coloring problem. International Journal of Foundations of Computer Science 13(3) 459-471, 2002.
  12. Jean Berstel and Juhani Karhumäki. Combinatorics on words: a tutorial. Bulletin of the EATCS, 79:178-, 2003.
  13. Tero Harju and Juhani Karhumäki. Many aspects of defect theorems. Theoret. Comput. Sci., 324(1):35-54, 2004.
  14. Svante Janson, Tero Laihonen, On the size of identifying codes, J. Combin. Theory A 116:1087-1096, 2009.
  15. Juha Honkala: It is decidable whether the image of an N-rational sequence has a base, Journal of Number Theory 108 (2004) 209-216.
  16. Juhani Karhumäki and Jeffrey Shallit. Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A, 105(2):335-347, 2004.
  17. Alexander Okhotin. Boolean grammars. Information and Computation 194(1) 19-48, doi:10.1016/j.ic.2004.03.006.
  18. Juha Honkala: An n2-bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet, Journal of Computer and System Sciences 71 506-519, 2005.
  19. Iiro Honkala, Mark Karpovsky, Lev Levitin: On robust and dynamic identifying codes, IEEE Transactions on Information Theory 52 599-612, 2006.
  20. Iiro Honkala: An optimal locating-dominating set in the infinite triangular grid, Discrete Math. 306 no. 21, 2670-2681, 2006.
  21. Tero Harju and Dirk Nowotka. Periodicity and unbordered words: a proof of the extended Duval conjecture. J. Assoc. Comput. Mach., 54(4), 2007.
  22. Leonard Adleman, Jarkko Kari, Lila Kari, Dustin Reishus, Petr Sosik. The Undecidabilitiy of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly. SIAM Journal on Computing, 38(6) 2356-2381, 2009.
  23. Juhani Karhumäki, Michal Kunc and Alexander Okhotin. Computational power of two stacks with restricted communication. Information and Computation 208 (2010) 1060-1089. doi:10.1016/j.ic.2009.07.001
  24. A. Okhotin. Decision problems for language equations, Journal of Computer and System Sciences, 76:3-4 (2010), 251-266.
  25. Juha Honkala: The equality problem for purely substitutive words. Chapter 10 in V. Berthe and M. Rigo (eds.): Combinatorics, Automata and Number Theory, Cambridge University Press 2010, pp. 505-529.
  26. Volker Diekert, Tero Harju and Dirk Nowotka. Weinbaum factorizations of primitive words (Russian), Izvestiya Vuzov. Matematika 2010 (1), 21-33; In English: Russian Mathematics (Iz VUZ) 54 (1), 16-25.
  27. Juhani Karhumäki, Aleksi Saarela. Maximum chains of systems of equations. In Specia issue dedicated to 80th birthday of Academician S. Adian (to appear)
  28. Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Balance and Abelian Complexity of the Tribonacci Word. Adv. Appl. Math. 45(2), 212--231, 2010.
  29. Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Abelian Complexity in Minimal Subshifts. To appear in J. Lond. Math. Soc.
  30. R. Vehkalahti, C. Hollanti, J. Lahtonen, K. Ranto: On the densest MIMO lattices from cyclic division algebras, IEEE Transactions on Information Theory, Vol. 55, no. 8, pp. 3751-3780, 2009.
  31. Aleksi Saarela: On the complexity of Hmelevskii's theorem and satisfiability of three unknown equations. Proceedings of the 13th International Conference on Developments in Language Theory, 443-453, 2009.
  32. Mari Huova, Juhani Karhumäki and Aleksi Saarela: Problems in between words and abelian words: k-abelian avoidability. Theoretical Computer Science, to appear.
  33. A. Gajardo, J. Kari, A. Moreira. On Time-symmetry in Cellular Automata. Journal of Computer and System Sciences 78(4), 1115--1126, 2012.

Last modified: Tuesday October 07, 2014