Publications of Mika Hirvensalo



  1. Mika Hirvensalo:The Reversibility in Quantum Computation Theory. Proceedings of the 3rd International Conference Developments in Language Theory - DLT'97, Ed.: Symeon Bozapalidis, Aristotle University of Thessaloniki, 203-210 (1997). [2]
  2. Mika Hirvensalo: On Quantum Computation. Licentiate's thesis, University of Turku. (1997). [5] Also as TUCS TR111.
  3. Mika Hirvensalo:Copying quantum computer makes NP-complete problems tractable. Proceedings of MCU'98, Vol II, edited by M. Margenstern (1998). [2] Preliminary version as TUCS TR161.
  4. Vesa Halava, Mika Hirvensalo, and Ronald de Wolf: Decidability and undecidability of marked PCP. LNCS 1563 (Proceedings of STACS'99), 207-216 (1999). [2] Preliminary version as TUCS TR201.
  5. Vesa Halava, Tero Harju, and Mika Hirvensalo: Generalized PCP is Decidable for Marked Morphisms. LNCS 1684 (Proceedings of FCT'99), 304-315 (1999). [2] Preliminary version as TUCS TR283.
  6. Vesa Halava, Tero Harju, and Mika Hirvensalo: Generalized Post Correspondence Problem for marked Morphisms. International Journal of Algebra and Computation 10:6, 757-772 , (2000). [1]
  7. Vesa Halava, Mika Hirvensalo, and Ronald de Wolf: Marked PCP is decidable. Theoretical Computer Science 255:1-2, 193-204, (2001). [1]
  8. Mika Hirvensalo: Quantum Computing, a monograph, xi+190 pp. Springer Series on Natural Computing (2001). [5]
  9. Mika Hirvensalo: An Introduction to Quantum Computing. In G. Paun, G. Rozenberg, A. Salomaa (eds.): Current Trends in Theoretical Computer Science - Entering the 21st Century, World Scientific, 643-663 (2001). [2] Preliminary version in Bulletin of the EATCS 66, 100-121 (1998).
  10. Mika Hirvensalo: Quantum Computing - Facts and Folklore. International Journal of Natural Computing 1, 135-155 (2002). [1]
  11. Vesa Halava, Tero Harju, and Mika Hirvensalo: Binary (generalized) Post Correspondence Problem. Theoretical Computer Science 276:1-2, 183-204 (2002). [1] Preliminary version as TUCS TR357.
  12. Mika Hirvensalo: Computing with Quanta - Impacts of Quantum Theory on Computation. Theoretical Computer Science 287:1, 267-298 (2002). [1] Preliminary version as TUCS TR386.
  13. Mika Hirvensalo and Juhani Karhumäki: Computing partial information out of intractable one - The first digit of 2n at base 3 as an example. LNCS 2420 (Proceedings of MFCS 2002), 319-327 (2002). [2] Preliminary version as TUCS TR446.
  14. Mika Hirvensalo: Universality and Quantum Computing. Bulletin of the EATCS 78: 199-203 (2002). [2]
  15. Mika Hirvensalo: Studies on Boolean Functions Related to Quantum Computing. Ph. D. thesis, University of Turku (2003). [5]
  16. Mika Hirvensalo: Tarinoita kvanttilaskennasta. Tietojenkäsittelytiede 19: 29-53 (2003) (in finnish). [6]
  17. Mika Hirvensalo and Sebastian Seibert: Lower bounds for Las Vegas Automata by Information Theory. Theoretical Informatics and Applications 37, 39-49, (2003). [1]
  18. Mika Hirvensalo: Quantum Computing, a monograph, xiii+214 pp. (2nd edition, 1st edition appeared in 2001). Springer Series on Natural Computing (2003) [5]
  19. Mika Hirvensalo: Some Open Problems Related to Quantum Computing. In G. Paun, G. Rozenberg, A. Salomaa (eds.): Current Trends in Theoretical Computer Science-The Challenge of the New Century, Vol 1, World Scientific (2004). [2] Preliminary version in Bulletin of the EATCS 74, 154-170 (2001)
  20. Mika Hirvensalo and Jyrki Lahtonen: On Self-dual Bases of the Extensions of the Binary Field. In J. Karhumäki, H. Maurer, G. Paun, G. Rozenberg (Eds.): Theory Is Forever: Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday. LNCS 3113, 102-111 (2004). [6]
  21. Mika Hirvensalo: P vs NP. Dimensio 5/04, pp. 16-20 (2004) (in finnish). [6]
  22. Mika Hirvensalo: Kvanttimekaniikan epälokaalisuus ja taikaneliöpeli. Arkhimedes 4/05, pp. 23-26 (2005) (in finnish). [6]
  23. Vesa Halava, Tero Harju, and Mika Hirvensalo: Positivity of Second Order Linear Recurrent Sequences. Discrete Applied Mathematics 154, 447-451 (2005) [1]. Preliminary version as TUCS TR685.
  24. Mika Hirvensalo: Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages. LNCS 4362, 309-319 (Proceedings of SOFSEM 2007) (2007). [2] Preliminary version as TUCS TR769.
  25. Mika Hirvensalo: EPR Paradox and Bell Inequalities. Bulletin of the EATCS 92, 115-139 (2007) [6]
  26. Vesa Halava and Mika Hirvensalo: Improved Matrix Pair Undecidability Results. Acta Informatica 44, 191-205 (2007). [1] Preliminary version as TUCS TR799.
  27. Vesa Halava, Tero Harju, and Mika Hirvensalo: Undecidability Bounds for Integer Matrices using Claus Instances. International Journal of Foundations of Computer Science 18:5 931-948 (2007) [1]. Preliminary version as TUCS TR766.
  28. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki: Post Correspondence Problem for short words. Information Processing Letters 108:3, 115-118 (2008) [1]
  29. Mika Hirvensalo: Various Aspects of Finite Quantum Automata. LNCS 5257 (Proceedings of DLT 2008), pp. 21-33 (2008). [2]
  30. Mika Hirvensalo, Juhani Karhumäki, and Alexander Rabinovich: Computing Partial Information out of Intractable: Powers of Algebraic Numbers as an Example. Journal of Number Theory 130, 232-253 (2010). Preliminary version as TUCS TR651 [1]
  31. Mika Hirvensalo: Quantum Automata with Open Time Evolution. International Journal of Natural Computing Research 1, 70-85 (2010). [1]
  32. Paul Bell, Vesa Halava, and Mika Hirvensalo: On the Joint Spectral Radius for Bounded Matrix Languages. LNCS 6227, 91-103 (2010). [2]
  33. Mika Hirvensalo: Quantum Automata Theory - A Review. LNCS 7020, 146-167 (2011). [2]
  34. Mika Hirvensalo: On probabilistic and quantum reaction systems. Theoretical Computer Science 429, pp.134-143 (2012) [1].
  35. Nikita Gogin and Mika Hirvensalo: Recurrent Construction of MacWilliams and Chebyshev Matrices. Fundamenta Informaticae 116, pp. 93-110 (2012) [1]. Preliminary version as TUCS TR812
  36. Paul Bell, Mika Hirvensalo, and Igor Potapov: Mortality for 2× 2 Matrices is NP-hard. LNCS 7464, 148-159 (2012). [2]
  37. Mika Hirvensalo: Mathematics for Quantum Information Processing. In G. Rozenberg, T. Bäck, J. Kok (eds.): Handbook of Natural Computing. Springer (2012). [5]
  38. Paul Bell, Vesa Halava, and Mika Hirvensalo: Decision Problems for Probabilistic Finite Automata on Bounded Languages. Fundamenta Informaticae 123:1, 1-14 (2013) [1]
  39. Mika Hirvensalo: Quantum Computing. In A. Runehov and L. Oviedo (eds.): Encyclopedia of Sciences and Religions. Springer (2013). [6]
  40. Mika Hirvensalo and Abuzer Yakaryılmaz (eds.): Proceedings of Workshop on Quantum and Classical Complexity. Latvian University Press (2013).
  41. Mika Hirvensalo: Geometric Toos for Automata Complexity. In: M. Hirvensalo and A. Yakaryılmaz (eds.): Proceedings of Workshop on Quantum and Classical Complexity. Latvian University Press (2013). [6]
  42. Mika Hirvensalo: Quantum and Biocomputing - Common Notions and Targets. In N. Kasabov (ed.): Springer Handbook of Bio-/Neuroinformatics (2014). [2]
  43. H. Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt, A. C. Cem Say, and Abuzer Yakaryılmaz: Classical and quantum realtime alternating automata. Proceedings of NCMA 2014, pp. 101-114 (2014). [2]
  44. Mika Hirvensalo and Abuzer Yakaryılmaz: Decision Problems on Unary Probabilistic and Quantum Automata. Baltic Journal of Modern Computing 4:4, pp. 965-976 (2016).
  45. Paul Bell, Mika Hirvensalo, and Igor Potapov: The Identity Problem for Matrix Semigroups in SL(2,Z) is NP-complete. Proceedings of AMC-SIAM Symposium on Discrete Algorithms (SODA 17), pp. 187-206 (2017).
  46. Mika Hirvensalo, Etienne Moutot, and Abuzer Yakaryılmaz: On the computational power of affine automata. LNCS 10168 (Proceedings of LATA 2017), pp. 405-417 (2017).
  47. N. Gogin and M. Hirvensalo: On the generating function of discrete Chebyshev polynomials. Journal of Mathematical Sciences 224(2), pp. 250-257 (2017).
    Conference version in Zap. Nauchn. Sem. POMI. Volume 448, pp. 124-134, (2016).
  48. Mika Hirvensalo: Interference as a computational resource: a tutorial. Natural Computing 17(1), 201-219 (2018).
  49. Mika Hirvensalo, Etienne Moutot, and Abuzer Yakaryılmaz: Computational Limitations of Affine Automata. In: Ian McQuillan and Shinnosuke Seki (eds.) LNCS 11493 (Proceedings of UCNC 2019), pp 108-121 (2019).
  50. Mika Hirvensalo and Abuzer Yakaryılmaz (eds): Proceedings of Workshop on Quantum Computing and Quantum Information. TUCS Lecture notes 30 (2019).
  51. Paul Bell and Mika Hirvensalo: Acceptance Ambiguity for Quantum Automata. In: Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen (Eds.): Proceedings of MFCS 2019. Leibniz International Proceedings in Informatics Vol. 138 (2019).
  52. Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt, A. C. Cem Say, and Abuzer Yakaryılmaz: Alternating, Private Alternating, and Quantum Alternating Realtime Automata. Logical Methods in Computer Science 15:3, pp. 22:1-22:21 (2019).
  53. Nikita Gogin, Mika Hirvensalo: On the Moments of Squared Binomial Coefficients. Proceedings of the PCA 2020.
  54. Mika Hirvensalo, Etienne Moutot, Abuzer Yakaryılmaz: Computational limitations of affine automata and generalized affine automata. Natural Computing 20(2): 259-270 (2021).
  55. Mika Hirvensalo, František Mráz, Daniel Průša: (eds): Non-Classical Models of Automata and Applications IX (Prodceedings of NCMA 2017 ). Fundamenta Informaticae 180, no. 1-2, pp. v-vi (2021)
  56. Nikita Gogin, Mika Hirvensalo: Riemann Hypothesis Analogue for Krawtchouk and Discrete Chebyshev Polynomials. Procedings of the PCA 2021.
  57. Paul C. Bell, Mika Hirvensalo: On injectivity of quantum finite automata. Journal of Computer and System Sciences. 122: 19-33 (2021).
  58. Nikita Gogin, Mika Hirvensalo: Riemann Hypothesis Property for The Convergents of a Continued Fraction Expansion . Polynomial Computer Algebra, 33, (2022).
  59. Paul C. Bell, Mika Hirvensalo, and Igor Potapov: The membership problem for subsemigroups of GL2(Z) is NP-complete. Information and Computation 296, 105132 (2024).
  60. Mika Hirvensalo, Akitoshi Kawamura, Igor Potapov, and Takao Yuyama: Reachability in Linear Recurrence Automata. LNCS 15050 (Proceedings of RP 2024), pp. 167-183, (2024).


    61. Under construction:

  61. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki: Skolem's problem - On the Border Between Decidability and Undecidability, TUCS TR683, submitted. [6]
  62. Mika Hirvensalo: A Method for Computing Characteristic Polynomial and Determining Semidefiniteness, TUCS TR727. [6] Seminar talk Dec 9. 2005 (slides in ps format), in progress.
  63. Mika Hirvensalo: Quantum Information Theory, a monograph.

Numbers in brackets:
  1. Articles in international scientific journals with referee practice
  2. Articles in international compilation works and in international scientific conference proceedings with referee practice
  3. Articles in Finnish scientific journals with referee practice
  4. Articles in Finnish scientific compilation works and in Finnish scientific conference proceedings with referee practice
  5. Scientific monographs
  6. Other scientific publications, such as articles in scientific journals, and conference proceedings without referee practice, and publications in university and department series.

Book Reviews

Minicourses

  1. Quantum Computing: Principles and Basic Algorithms. Thessaloniki, Greece May 16-19, 2006.
  2. Quantum Computing: Advanced Tutorial. Turku, Finland, June 26, 2006 (A satellite event to ACSD & Petri Nets 2006).
  3. Tutorial on Quantum Computing. Prague, Czech Republic, September 2008
  4. Tutorial on Quantum Information. Unconventional Computation 2011, Turku, Finland, June 2011
  5. Lectures on Quantum Information, Quantum Computing, and Quantum Cryptography. Kazan, Russia, September 2011
  6. Quantum Computing and Quantum Information Theory. Thessaloniki, Greece, May 7-10, 2012.
  7. Quantum Computing and Quantum Information Theory. Thessaloniki, Greece, May 13-16, 2014.
  8. Quantum Computing and Quantum Information Theory. Thessaloniki, Greece, May 16-19, 2016.

Conference participation (<= Click here to see)

Old seminar talks, lecture notes, etc.

  1. Coding theory seminar 1996: On Galois rings and Z4-linear codes Part 1, Part 2, Part 3, Part 4, Part 5
  2. Seminar on Automata 1996: The undecidability of the inclusion of N-subsets
  3. Seminar on Harmonic analysis 1996 (in finnish): Part 1, Part 2, Part 3, Part 4, Part 5
  4. Seminar talks on quantum computing: Part 1, Part 2, Part 3.
  5. Zeta functions on algebraic number fields (in finnish): Part 1, Part 2, Part 3
  6. Ordering the free groups
  7. On transcendental field extensions (in finnish)
  8. Seminar on Hilbert's Tenth Problem: Exponentiation is Diophatine
  9. Seminar on Cohomology algebra (in finnish): Part 1, Part 2
  10. On computability (in finnish)
  11. On quantum cryptography
  12. Quantum error correction, TUCS TR178
  13. Applications of discrete Fourier analysis in F2n (in finnish)
To my homepage