Vesa Halava

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 19

Top Topics

Decision Problems

Top Venues

Fundam. Informaticae

Theor. Comput. Sci.

Int. J. Found. Comput. Sci.

Publications

Vesa Halava, Jarkko Kari, Tero Laihonen
Preface. Fundam. Informaticae 191 (3-4) (2024)
Vesa Halava, Tero Harju, Dirk Nowotka, Esa Sahla
Decision Problems on Copying and Shuffling. Fundam. Informaticae 191 (3-4) (2024)
Vesa Halava, Stepan Holub
Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time. Int. J. Found. Comput. Sci. 35 (1&2) (2024)
Vesa Halava, Reino Niskanen
On simulating Turing machines with matrix semigroups with integrality tests. Theor. Comput. Sci. 1005 (2024)
Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov
Integer Weighted Automata on Infinite Words. Int. J. Found. Comput. Sci. 34 (2&3) (2023)
Olivier Finkel, Vesa Halava, Tero Harju, Esa Sahla
On bi-infinite and conjugate post correspondence problems. RAIRO Theor. Informatics Appl. 57 (2023)
Vesa Halava, Tero Harju, Dirk Nowotka, Esa Sahla
Decision Problems on Copying and Shuffling. CoRR (2023)
Vesa Halava, Tero Harju, Teemu Pirttimäki
A recursive function coding number theoretic functions. CoRR (2022)
Vesa Halava, Tero Harju, Esa Sahla
The Conjugate Post Correspondence Problem. CoRR (2021)
Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov
Integer Weighted Automata on Infinite Words. DLT (2021)
Vesa Halava
Undecidability in Finite Transducers, Defense Systems and Finite Substitutions. CoRR (2021)
Vesa Halava, Tero Harju
On the Steps of Emil Post: from Normal Systems to the Correspondence Decision Problem. Acta Cybern. 24 (4) (2020)
Vesa Halava, Tero Harju, Esa Sahla
On Shuffling a Word with its Letter-to-Letter Substitution. Fundam. Informaticae 175 (1-4) (2020)
Vesa Halava, Juhani Karhumäki, Yuri V. Matiyasevich, Mikhail V. Volkov
Perface. Fundam. Informaticae 162 (2-3) (2018)
Vesa Halava, Tero Harju, Esa Sahla
On fixed points of rational transductions. Theor. Comput. Sci. 732 (2018)
Vesa Halava, Tero Harju
Walks on tilings of polygons. Theor. Comput. Sci. 701 (2017)
Vesa Halava, Tero Harju, Esa Sahla
A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem. Fundam. Informaticae 154 (1-4) (2017)
Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov
Weighted automata on infinite words in the context of Attacker-Defender games. Inf. Comput. 255 (2017)
Vesa Halava, Yuri V. Matiyasevich, Reino Niskanen
Small Semi-Thue System Universal with Respect to the Termination Problem. Fundam. Informaticae 154 (1-4) (2017)
Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov
Weighted Automata on Infinite Words in the Context of Attacker-Defender Games. CiE (2015)
Mari Ernvall, Vesa Halava, Tero Harju
On the n-permutation Post Correspondence Problem. Theor. Comput. Sci. 601 (2015)
Vesa Halava, Reino Niskanen, Igor Potapov
On Robot Games of Degree Two. LATA (2015)
Julien Cassaigne, Vesa Halava, Tero Harju, François Nicolas
Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More. CoRR (2014)
Vesa Halava, Juhani Karhumäki, Yuri V. Matiyasevich
Preface. Fundam. Informaticae 132 (1) (2014)
Vesa Halava, Reino Niskanen, Igor Potapov
On Undecidability of Counter Reachability Games in Dimension One. CoRR (2014)
Vesa Halava
Another proof of undecidability for the correspondence decision problem - Had I been Emil Post. CoRR (2014)
Paul C. Bell, Vesa Halava, Mika Hirvensalo
Decision Problems for Probabilistic Finite Automata on Bounded Languages. Fundam. Informaticae 123 (1) (2013)
Vesa Halava
Deterministic Semi-Thue Systems and Variants of Post Correspondence Problem. WORDS (2013)
Vesa Halava, Tero Harju
New proof for the undecidability of the circular PCP. Acta Informatica 50 (5-6) (2013)
Vesa Halava, Juhani Karhumäki, Dirk Nowotka, Grzegorz Rozenberg
Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero Harju. Fundam. Informaticae 116 (1-4) (2012)
Vesa Halava, Stepan Holub
Reduction Tree of the Binary Generalized Post Correspondence Problem. Int. J. Found. Comput. Sci. 22 (2) (2011)
Vesa Halava, Tero Harju, Tomi Kärki
A new proof for the decidability of D0L ultimate periodicity WORDS (2011)
Paul Bell, Vesa Halava, Mika Hirvensalo
On the Joint Spectral Radius for Bounded Matrix Languages. RP (2010)
Vesa Halava, Tero Harju, Tomi Kärki, Michel Rigo
On the Periodicity of Morphic Words. Developments in Language Theory (2010)
Vesa Halava, Tero Harju, Tomi Kärki
On the number of squares in partial words. RAIRO Theor. Informatics Appl. 44 (1) (2010)
Vesa Halava, Tero Harju, Tomi Kärki, Patrice Séébold
Overlap-freeness in infinite partial words. Theor. Comput. Sci. 410 (8-10) (2009)
Vesa Halava, Igor Potapov
Preface. Int. J. Found. Comput. Sci. 20 (5) (2009)
Vesa Halava, Tero Harju, Tomi Kärki
The theorem of Fine and Wilf for relational periods. RAIRO Theor. Informatics Appl. 43 (2) (2009)
Vesa Halava, Jarkko Kari, Yuri V. Matiyasevich
On post correspondence problem for letter monotonic languages. Theor. Comput. Sci. 410 (30-32) (2009)
Vesa Halava, Igor Potapov
Preface. Electron. Notes Theor. Comput. Sci. 223 (2008)
Vesa Halava, Tero Harju, Mika Hirvensalo, Juhani Karhumäki
Post Correspondence Problem for short words. Inf. Process. Lett. 108 (3) (2008)
Vesa Halava, Tero Harju, Tomi Kärki
Square-free partial words. Inf. Process. Lett. 108 (5) (2008)
Vesa Halava, Igor Potapov
Preface. Int. J. Found. Comput. Sci. 19 (4) (2008)
Tomi Kärki, Tero Harju, Vesa Halava
Interaction Properties of Relational Periods. Discret. Math. Theor. Comput. Sci. 10 (1) (2008)
Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, Igor Potapov
Matrix Equations and Hilbert's Tenth Problem. Int. J. Algebra Comput. 18 (8) (2008)
Vesa Halava, Tero Harju, Mika Hirvensalo
Undecidability Bounds for Integer Matrices Using Claus Instances. Int. J. Found. Comput. Sci. 18 (5) (2007)
Vesa Halava, Tero Harju, Tomi Kärki
Relational codes of words. Theor. Comput. Sci. 389 (1-2) (2007)
Vesa Halava, Tero Harju, Juhani Karhumäki, Michel Latteux
Extension of the decidability of the marked PCP to instances with unique blocks. Theor. Comput. Sci. 380 (3) (2007)
Vesa Halava, Mika Hirvensalo
Improved matrix pair undecidability results. Acta Informatica 44 (3-4) (2007)
Vesa Halava, Tero Harju, Juhani Karhumäki
The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems. Theory Comput. Syst. 40 (1) (2007)
Vesa Halava, Tero Harju
Undecidability of infinite post correspondence problem for instances of Size 9. RAIRO Theor. Informatics Appl. 40 (4) (2006)
Vesa Halava, Tero Harju, Mika Hirvensalo
Positivity of second order linear recurrent sequences. Discret. Appl. Math. 154 (3) (2006)
Vesa Halava, Tero Harju, Juhani Karhumäki
Undecidability in omega-Regular Languages. Fundam. Informaticae 73 (1-2) (2006)
Vesa Halava, Tero Harju, Michel Latteux
Representation of Regular Languages by Equality Sets. Bull. EATCS 86 (2005)
Vesa Halava, Tero Harju, Michel Latteux
Equality sets of prefix morphisms and regular star languages. Inf. Process. Lett. 94 (4) (2005)
Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux
Equality sets for recursively enumerable languages. RAIRO Theor. Informatics Appl. 39 (4) (2005)
Vesa Halava, Tero Harju
Undecidability in matrices over Laurent polynomials. Adv. Appl. Math. 33 (4) (2004)
Vesa Halava
Integer Weighted Finite Automata, Matrices, and Formal Power Series over Laurent Polynomials. Theory Is Forever (2004)
Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux
Valence Languages Generated by Equality Sets. J. Autom. Lang. Comb. 9 (4) (2004)
Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux
Languages Defined by Generalized Equality Sets. FCT (2003)
Vesa Halava, Tero Harju, Juhani Karhumäki
Decidability of the binary infinite Post Correspondence Problem. Discret. Appl. Math. 130 (3) (2003)
Vesa Halava, Tero Harju
Infinite Solutions of Marked Post Correspondence Problem. Formal and Natural Computing (2002)
Vesa Halava, Tero Harju, Mika Hirvensalo
Binary (generalized) Post Correspondence Problem. Theor. Comput. Sci. 276 (1-2) (2002)
Vesa Halava, Tero Harju
An Undecidability Result Concerning Periodic Morphisms. Developments in Language Theory (2001)
Vesa Halava, Tero Harju
Some New Results on Post Correspondence Problem and Its Modifications. Bull. EATCS 73 (2001)
Vesa Halava, Mika Hirvensalo, Ronald de Wolf
Marked PCP is decidable. Theor. Comput. Sci. 255 (1-2) (2001)
Vesa Halava, Tero Harju
Mortality in Matrix Semigroups. Am. Math. Mon. 108 (7) (2001)
Vesa Halava, Tero Harju, Lucian Ilie
Periods and Binary Words. J. Comb. Theory, Ser. A 89 (2) (2000)
Vesa Halava, Tero Harju, Mika Hirvensalo
Generalized Post Correspondence Problem for Marked Morphisms. Int. J. Algebra Comput. 10 (6) (2000)
Vesa Halava, Tero Harju
Languages Accepted by Integer Weighted Finite Automata. Jewels are Forever (1999)
Vesa Halava, Tero Harju, Mika Hirvensalo
Generalized PCP Is Decidable for Marked Morphisms. FCT (1999)
Vesa Halava, Tero Harju
Undecidability of the equivalence of finite substitutions on regular language. RAIRO Theor. Informatics Appl. 33 (2) (1999)
Vesa Halava, Mika Hirvensalo, Ronald de Wolf
Decidability and Undecidability of Marked PCP. STACS (1999)
Vesa Halava, Tero Harju
Undecidability in Integer Weighted Finite Automata. Fundam. Informaticae 38 (1-2) (1999)
Vesa Halava, Tero Harju, Lucian Ilie
On a Geometric Problem of Zigzags. Inf. Process. Lett. 62 (1) (1997)