Mika Hirvensalo

According to our database, Mika Hirvensalo authored at least 52 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

The membership problem for subsemigroups of GL2(Z) is NP-complete.

Paul C. Bell, Mika Hirvensalo, Igor Potapov

Inf. Comput., January, 2024

Reachability in Linear Recurrence Automata.

Mika Hirvensalo, Akitoshi Kawamura, Igor Potapov, Takao Yuyama

Proceedings of the Reachability Problems - 18th International Conference, 2024

2021

Correction to: Computational limitations of affine automata and generalized affine automata.

Mika Hirvensalo, Etienne Moutot, Abuzer Yakaryilmaz

Nat. Comput., 2021

Computational limitations of affine automata and generalized affine automata.

Mika Hirvensalo, Etienne Moutot, Abuzer Yakaryilmaz

Nat. Comput., 2021

On injectivity of quantum finite automata.

Paul C. Bell, Mika Hirvensalo

J. Comput. Syst. Sci., 2021

2019

Alternating, private alternating, and quantum alternating realtime automata.

Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt, A. C. Cem Say, Abuzer Yakaryilmaz

Log. Methods Comput. Sci., 2019

Computational Limitations of Affine Automata.

Mika Hirvensalo, Etienne Moutot, Abuzer Yakaryilmaz

Proceedings of the Unconventional Computation and Natural Computation, 2019

Acceptance Ambiguity for Quantum Automata.

Paul C. Bell, Mika Hirvensalo

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

Interference as a computational resource: a tutorial.

Mika Hirvensalo

Nat. Comput., 2018

2017

The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete.

Paul C. Bell, Mika Hirvensalo, Igor Potapov

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Computational Power of Affine Automata.

Mika Hirvensalo, Etienne Moutot, Abuzer Yakaryilmaz

Proceedings of the Language and Automata Theory and Applications, 2017

2016

Preface.

Suna Bensch, Rudolf Freund, Mika Hirvensalo, Friedrich Otto

Fundam. Informaticae, 2016

Decision Problems on Unary Probabilistic and Quantum Automata.

Mika Hirvensalo, Abuzer Yakaryilmaz

Balt. J. Mod. Comput., 2016

2015

Preface.

Suna Bensch, Frank Drewes, Mika Hirvensalo, Friedrich Otto

Fundam. Informaticae, 2015

2014

Classical and quantum realtime alternating automata.

H. Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt, A. C. Cem Say, Abuzer Yakaryilmaz

Proceedings of the Sixth Workshop on Non-Classical Models for Automata and Applications, 2014

2013

Decision Problems for Probabilistic Finite Automata on Bounded Languages.

Paul C. Bell, Vesa Halava, Mika Hirvensalo

Fundam. Informaticae, 2013

2012

Mathematics for Quantum Information Processing.

Mika Hirvensalo

Proceedings of the Handbook of Natural Computing, 2012

On probabilistic and quantum reaction systems.

Mika Hirvensalo

Theor. Comput. Sci., 2012

Recurrent Construction of MacWilliams and Chebyshev Matrices.

Nikita Gogin, Mika Hirvensalo

Fundam. Informaticae, 2012

Mortality for 2×2 Matrices Is NP-Hard.

Paul C. Bell, Mika Hirvensalo, Igor Potapov

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

Preface.

Henning Bordihn, Rudolf Freund, Mika Hirvensalo, Markus Holzer, Martin Kutrib, Friedrich Otto

Fundam. Informaticae, 2011

Quantum Information - A Tutorial.

Mika Hirvensalo

Proceedings of the Unconventional Computation - 10th International Conference, 2011

Quantum Automata Theory - A Review.

Mika Hirvensalo

Proceedings of the Algebraic Foundations in Computer Science, 2011

2010

Quantum Automata with Open Time Evolution.

Mika Hirvensalo

Int. J. Nat. Comput. Res., 2010

On the Joint Spectral Radius for Bounded Matrix Languages.

Paul Bell, Vesa Halava, Mika Hirvensalo

Proceedings of the Reachability Problems, 4th International Workshop, 2010

2009

Preface.

Mika Hirvensalo

Theor. Comput. Sci., 2009

2008

Post Correspondence Problem for short words.

Vesa Halava, Tero Harju, Mika Hirvensalo, Juhani Karhumäki

Inf. Process. Lett., 2008

Various Aspects of Finite Quantum Automata.

Mika Hirvensalo

Proceedings of the Developments in Language Theory, 12th International Conference, 2008

2007

Undecidability Bounds for Integer Matrices Using Claus Instances.

Vesa Halava, Tero Harju, Mika Hirvensalo

Int. J. Found. Comput. Sci., 2007

EPR Paradox and Bell Inequalitites.

Mika Hirvensalo

Bull. EATCS, 2007

Phillip Kaye, Raymond Laflamme and Michele Mosca, An Introduction to Quantum Computing, Oxford University Press (2007) ISBN 019857049X.

Mika Hirvensalo

Comput. Sci. Rev., 2007

Improved matrix pair undecidability results.

Vesa Halava, Mika Hirvensalo

Acta Informatica, 2007

Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages.

Mika Hirvensalo

Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

2006

Positivity of second order linear recurrent sequences.

Vesa Halava, Tero Harju, Mika Hirvensalo

Discret. Appl. Math., 2006

2004

On Self-Dual Bases of the Extensions of the Binary Field.

Mika Hirvensalo, Jyrki T. Lahtonen

Proceedings of the Theory Is Forever, 2004

Quantum computing, Second Edition.

Mika Hirvensalo

Natural computing series, Springer, ISBN: 978-3-540-40704-1, 2004

2003

Lower Bounds for Las Vegas Automata by Information Theory.

Mika Hirvensalo, Sebastian Seibert

RAIRO Theor. Informatics Appl., 2003

2002

Computing with quanta - impacts of quantum theory on computation.

Mika Hirvensalo

Theor. Comput. Sci., 2002

Binary (generalized) Post Correspondence Problem.

Vesa Halava, Tero Harju, Mika Hirvensalo

Theor. Comput. Sci., 2002

Quantum computing - Facts and folklore.

Mika Hirvensalo

Nat. Comput., 2002

Universality and Quantum Computing.

Mika Hirvensalo

Bull. EATCS, 2002

Computing Partial Information out of Intractable One - The First Digit of 2ⁿ at Base 3 as an Example.

Mika Hirvensalo, Juhani Karhumäki

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001

Marked PCP is decidable.

Vesa Halava, Mika Hirvensalo, Ronald de Wolf

Theor. Comput. Sci., 2001

Some Open Problems Related to Quantum Computing.

Mika Hirvensalo

Bull. EATCS, 2001

An Introduction to Quantum Computing.

Mika Hirvensalo

Proceedings of the Current Trends in Theoretical Computer Science, 2001

Quantum computing.

Mika Hirvensalo

Natural computing series, Springer, ISBN: 978-3-540-66783-4, 2001

2000

Generalized Post Correspondence Problem for Marked Morphisms.

Vesa Halava, Tero Harju, Mika Hirvensalo

Int. J. Algebra Comput., 2000

1999

Decidability and Undecidability of Marked PCP.

Vesa Halava, Mika Hirvensalo, Ronald de Wolf

Proceedings of the STACS 99, 1999

Generalized PCP Is Decidable for Marked Morphisms.

Vesa Halava, Tero Harju, Mika Hirvensalo

Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999

1998

An Introduction to Quantum Computing.

Mika Hirvensalo

Bull. EATCS, 1998

Copying quantum computer makes NP-complete problems tractable.

Mika Hirvensalo

Proceedings of the International Colloquium Universal Machines and Computations, 1998

1997

The Reversibility in Quantum Computation Theory.

Mika Hirvensalo

Proceedings of the 3rd International Conference Developments in Language Theory, 1997