Fundamentals of Computing and Discrete Mathematics

Complex Systems and Computing
– Publications

  1. E.Formenti, J.Kari, S.Taati. On the Hierarchy of Conservation Laws in a Cellular Automaton. Natural Computing, to appear.
  2. P.Guillon. Canonical Factor of Cellular Automata. In: Cellular Automata (ed. T.M.Li), Nova Publishers, to appear.
  3. E.Goles, P.Guillon, I.Rapaport. Traced Communication Complexity of Cellular Automata. Theoretical Computer Science, to appear.
  4. P.Guillon, P.-É.Meunier, G, Theyssier. Clandestine Simulations in Cellular Automata. In: Proceedings of JAC 2010, Journées Automates Cellulaires (ed. J.Kari), to appear.
  5. Mika Hirvensalo: Quantum Automata with Open Time Evolution. International Journal of Natural Computing Research 1, pp. 70-85, (2010).
  6. Ville Lukkarila. Sensitivity and Topological Mixing are Undecidable for Reversible One-dimensional Cellular Automata. Journal of Cellular Automata, 5(3):241-272, 2010.
  7. L. Adleman, J. Kari, L. Kari, D. Reishus and P. Sosik. The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly. SIAM Journal on Computing 38(6), 2356-2381, 2009.
  8. V. Lukkarila. The 4-way deterministic tiling problem is undecidable. Theoretical Computer Science 410(16), 1516-1533, 2009.
  9. J. Kari, P. Vanier, T. Zeume. Bounds on non-surjective cellular automata. In: Proceedings of MFCS 2009: International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science 5734, 439-450, Springer-Verlag, 2009.
  10. J. Kari. Tiling Problem and Undecidability in Cellular Automata. In: Encyclopedia of Complexity and Systems Science. R.A. Meyers (Ed.), Springer, 9158-9172, 2009.
  11. J. Kari, V. Lukkarila. Some undecidable dynamical properties for one-dimensional reversible cellular automata. In: Algorithmic Bioprocesses. A. Condon, D. Harel, J.N. Kok, A. Salomaa and E. Winfree (Eds.), Springer, 639-660, 2009.
  12. L. Cappellari, C. Cruz-Reyes, G. Calvagno, J. Kari. Lossy to Lossless Spatially Scalable Depth Map Coding with Cellular Automata. In: Proceedings of the 2009 Data Compression Conference (DCC 2009). J.A. Storer, M.W. Marcellin (Eds.), IEEE Computer Society Press, 332-341, 2009.
  13. M.-P. Beal, E. Czeizler, J. Kari, D. Perrin. Unambiguous Automata. Mathematics in Computer Science 1(4), 625-638, 2008.
  14. T. Boykett, J. Kari and S. Taati. Conservation Laws in Rectangular CA. Journal of Cellular Automata 3(2), 115-122, 2008.
  15. J.Kari, N.Ollinger. Periodicity and Immortality in Reversible Computing. Proceedings of MFCS 2008: International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science 5162, 419-430, Springer-Verlag, 2008.
  16. C.Cruz-Reyes, J.Kari. Non-Linear Subband Coding with Cellular Automata. In: Proceedings of AFL 2008: Automata and Formal Languages. The 12th International Conference, Balatonfured, Hungary, May 27-30, 2008. Erzsebet Csuhaj-Varju and Zoltan Esik (Eds.) Published by the Computer and Automation Research Institute, Hungarian Academy of Sciences, pp. 146-157, May 2008.
  17. E. Formenti, J. Kari, S. Taati. The Most General Conservation Law for a Cellular Automaton. In: Proceedings of CSR 2008: Computer Science in Russia. Lecture Notes in Computer Science 5010, 194-203, Springer-Verlag, 2008.
  18. J. Kari. Undecidable properties on the dynamics of reversible one-dimensional cellular automata. In: Proceedings of JAC 2008: Journées Automates Cellulaires, 3-14, MCCME Publishing House Moscow. Also in: http://hal.archives-ouvertes.fr/JAC2008. 2008.
  19. J.Kari, S.Taati. A Particle Displacement Representation for Conservation Laws in Two-Dimensional Cellular Automata. In: Proceedings of JAC 2008: Journées Automates Cellulaires, 65-73, MCCME Publishing House Moscow. Also in: http://hal.archives-ouvertes.fr/JAC2008. 2008.
  20. J. Kari, S. Taati. Combinatorics of Conservation Laws. Bulletin of the European Association for Theoretical Computer Science 95, 183-197, 2008.
  21. V. Lukkarila. On undecidability of sensitivity of reversible cellular automata. In: Proceedings of Automata 2008, A. Adamatzky, R. Alonzo-Sanz, A. Lawniczak, G. Martinez, K. Morita ja T. Worsch (Eds.), 100-105, Luniver Press, 2008.
  22. Jarkko Kari. On the undecidability of the tiling problem. SOFSEM 2008: Theory and Practice of Computer Science. Lecture Notes in Comput. Sci. 4910, 74-82, Springer-Verlag, 2008.
  23. E. Czeizler, J. Kari. A tight linear bound on the synchronization delay of bijective automata. Theoretical Computer Science 380(1-2), 23-36, 2007.
  24. Siamak Taati. Cellular Automata Reversible over Limit Set. Journal of Cellular Automata, 2(2), 167-177, 2007.
  25. M. Hirvensalo. EPR Paradox and Bell Inequalities. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS No. 92: 115-139, 2007.
  26. M. Hirvensalo. Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages. Proceedings of SOFSEM 2007, Lecture Notes in Comput. Sci. 4362, 309-319, 2007.
  27. V. Bernardi, B. Durand, E. Formenti and J. Kari. A new dimension sensitive property for cellular automata. Theoret. Comput. Sci. 345(2-3):235-247, 2005.
  28. E. Czeizler and J. Kari. A tight linear bound on the neighborhood of inverse cellular automata. Proceedings of ICALP'05, Lecture Notes in Comput. Sci. 3580:410-420, 2005.
  29. J. Kari. Theory of cellular automata: a survey. Theoret. Comput. Sci. 334(1-3):3-33, 2005.
  30. E. Czeizler. On the size of the inverse neighborhoods for one-dimensional reversible cellular automata. Theoret. Comput. Sci. 325(2):273-284, 2004.
  31. A. Ehrenfeucht, T. Harju, I. Petre D. Prescott and G. Rozenberg. Computation in Living Cells. Springer-Verlag, Berlin, 2004.
  32. T. Harju, I. Petre and G. Rozenberg. Gene assembly in ciliates. II. Formal frameworks. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS No. 82:227-241, 2004.
  33. M. Hirvensalo. Quantum computing (2nd edition). Springer-Verlag, Berlin, 2004.
  34. T. Harju, I. Petre and G. Rozenberg. Gene assembly in ciliates. I. Molecular operations. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS No. 81:236-249, 2003.
  35. A. Ehrenfeucht, T. Harju, I. Petre, D.M. Prescott and G. Rozenberg. Formal systems for gene assembly in ciliates. Theoret. Comput. Sci. 292(1):199-219, 2003.
  36. A. Ehrenfeucht, T. Harju and G. Rozenberg. Gene assembly through cyclic graph decomposition. Theoret. Comput. Sci. 281(1-2):325-349, 2002.
  37. M. Hirvensalo. Universality and quantum computing. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS No. 78:199-203, 2002.
  38. M. Hirvensalo. Computing with quanta - impacts of quantum theory on computation. Theoret. Comput. Sci. 287(1):267-298, 2002.
  39. M. Hirvensalo. Quantum computing - facts and folklore. Nat. Comput. 1(1):135-155, 2002.
  40. L.M. Adleman, J. Kari, L. Kari and D. Reishus. On the Decidability of Self-Assembly of Infinite Ribbons. Proceedings of FOCS 2002: 530-537, 2002.
  41. M. Hirvensalo. Some open problems related to quantum computing. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS No. 74:154-170, 2001.
Last modified: