Vesa Halava

According to our database, Vesa Halava authored at least 70 papers between 1997 and 2024.

Collaborative distances:

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

2024

On simulating Turing machines with matrix semigroups with integrality tests.

Vesa Halava, Reino Niskanen

Theor. Comput. Sci., 2024

Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time.

Vesa Halava, Stepan Holub

Int. J. Found. Comput. Sci., 2024

Preface.

Vesa Halava, Jarkko Kari, Tero Laihonen

Fundam. Informaticae, 2024

Decision Problems on Copying and Shuffling.

Vesa Halava, Tero Harju, Dirk Nowotka, Esa Sahla

Fundam. Informaticae, 2024

2023

On bi-infinite and conjugate post correspondence problems.

Olivier Finkel, Vesa Halava, Tero Harju, Esa Sahla

RAIRO Theor. Informatics Appl., 2023

Integer Weighted Automata on Infinite Words.

Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov

Int. J. Found. Comput. Sci., 2023

2022

A recursive function coding number theoretic functions.

Vesa Halava, Tero Harju, Teemu Pirttimäki

CoRR, 2022

2021

Undecidability in Finite Transducers, Defense Systems and Finite Substitutions.

Vesa Halava

CoRR, 2021

The Conjugate Post Correspondence Problem.

Vesa Halava, Tero Harju, Esa Sahla

CoRR, 2021

2020

On Shuffling a Word with its Letter-to-Letter Substitution.

Vesa Halava, Tero Harju, Esa Sahla

Fundam. Informaticae, 2020

On the Steps of Emil Post: from Normal Systems to the Correspondence Decision Problem.

Vesa Halava, Tero Harju

Acta Cybern., 2020

2018

On fixed points of rational transductions.

Vesa Halava, Tero Harju, Esa Sahla

Theor. Comput. Sci., 2018

Perface.

Vesa Halava, Juhani Karhumäki, Yuri V. Matiyasevich, Mikhail V. Volkov

Fundam. Informaticae, 2018

2017

Walks on tilings of polygons.

Vesa Halava, Tero Harju

Theor. Comput. Sci., 2017

Weighted automata on infinite words in the context of Attacker-Defender games.

Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov

Inf. Comput., 2017

Small Semi-Thue System Universal with Respect to the Termination Problem.

Vesa Halava, Yuri V. Matiyasevich, Reino Niskanen

Fundam. Informaticae, 2017

A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem.

Vesa Halava, Tero Harju, Esa Sahla

Fundam. Informaticae, 2017

2015

On the n-permutation Post Correspondence Problem.

Mari Ernvall, Vesa Halava, Tero Harju

Theor. Comput. Sci., 2015

On Robot Games of Degree Two.

Vesa Halava, Reino Niskanen, Igor Potapov

Proceedings of the Language and Automata Theory and Applications, 2015

2014

Preface.

Vesa Halava, Juhani Karhumäki, Yuri V. Matiyasevich

Fundam. Informaticae, 2014

On Undecidability of Counter Reachability Games in Dimension One.

Vesa Halava, Reino Niskanen, Igor Potapov

CoRR, 2014

Another proof of undecidability for the correspondence decision problem - Had I been Emil Post.

Vesa Halava

CoRR, 2014

Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More.

Julien Cassaigne, Vesa Halava, Tero Harju, François Nicolas

CoRR, 2014

2013

Decision Problems for Probabilistic Finite Automata on Bounded Languages.

Paul C. Bell, Vesa Halava, Mika Hirvensalo

Fundam. Informaticae, 2013

New proof for the undecidability of the circular PCP.

Vesa Halava, Tero Harju

Acta Informatica, 2013

Deterministic Semi-Thue Systems and Variants of Post Correspondence Problem.

Vesa Halava

Proceedings of the Combinatorics on Words - 9th International Conference, 2013

2012

Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero Harju.

Vesa Halava, Juhani Karhumäki, Dirk Nowotka, Grzegorz Rozenberg

Fundam. Informaticae, 2012

2011

Reduction Tree of the Binary Generalized Post Correspondence Problem.

Vesa Halava, Stepan Holub

Int. J. Found. Comput. Sci., 2011

A new proof for the decidability of D0L ultimate periodicity

Vesa Halava, Tero Harju, Tomi Kärki

Proceedings of the Proceedings 8th International Conference Words 2011, 2011

2010

On the number of squares in partial words.

Vesa Halava, Tero Harju, Tomi Kärki

RAIRO Theor. Informatics Appl., 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

On the Periodicity of Morphic Words.

Vesa Halava, Tero Harju, Tomi Kärki, Michel Rigo

Proceedings of the Developments in Language Theory, 14th International Conference, 2010

2009

On post correspondence problem for letter monotonic languages.

Vesa Halava, Jarkko Kari, Yuri V. Matiyasevich

Theor. Comput. Sci., 2009

Overlap-freeness in infinite partial words.

Vesa Halava, Tero Harju, Tomi Kärki, Patrice Séébold

Theor. Comput. Sci., 2009

The theorem of Fine and Wilf for relational periods.

Vesa Halava, Tero Harju, Tomi Kärki

RAIRO Theor. Informatics Appl., 2009

2008

Square-free partial words.

Vesa Halava, Tero Harju, Tomi Kärki

Inf. Process. Lett., 2008

Post Correspondence Problem for short words.

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

Inf. Process. Lett., 2008

Preface.

Vesa Halava, Igor Potapov

Int. J. Found. Comput. Sci., 2008

Matrix Equations and Hilbert's Tenth Problem.

Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, Igor Potapov

Int. J. Algebra Comput., 2008

Interaction Properties of Relational Periods.

Tomi Kärki, Tero Harju, Vesa Halava

Discret. Math. Theor. Comput. Sci., 2008

2007

Extension of the decidability of the marked PCP to instances with unique blocks.

Vesa Halava, Tero Harju, Juhani Karhumäki, Michel Latteux

Theor. Comput. Sci., 2007

Relational codes of words.

Vesa Halava, Tero Harju, Tomi Kärki

Theor. Comput. Sci., 2007

The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems.

Vesa Halava, Tero Harju, Juhani Karhumäki

Theory Comput. Syst., 2007

Undecidability Bounds for Integer Matrices Using Claus Instances.

Vesa Halava, Tero Harju, Mika Hirvensalo

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

Improved matrix pair undecidability results.

Vesa Halava, Mika Hirvensalo

Acta Informatica, 2007

2006

Undecidability of infinite post correspondence problem for instances of Size 9.

Vesa Halava, Tero Harju

RAIRO Theor. Informatics Appl., 2006

Undecidability in omega-Regular Languages.

Vesa Halava, Tero Harju, Juhani Karhumäki

Fundam. Informaticae, 2006

Positivity of second order linear recurrent sequences.

Vesa Halava, Tero Harju, Mika Hirvensalo

Discret. Appl. Math., 2006

2005

Equality sets for recursively enumerable languages.

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux

RAIRO Theor. Informatics Appl., 2005

Equality sets of prefix morphisms and regular star languages.

Vesa Halava, Tero Harju, Michel Latteux

Inf. Process. Lett., 2005

Representation of Regular Languages by Equality Sets.

Vesa Halava, Tero Harju, Michel Latteux

Bull. EATCS, 2005

2004

Valence Languages Generated by Equality Sets.

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux

J. Autom. Lang. Comb., 2004

Undecidability in matrices over Laurent polynomials.

Vesa Halava, Tero Harju

Adv. Appl. Math., 2004

Integer Weighted Finite Automata, Matrices, and Formal Power Series over Laurent Polynomials.

Vesa Halava

Proceedings of the Theory Is Forever, 2004

2003

Decidability of the binary infinite Post Correspondence Problem.

Vesa Halava, Tero Harju, Juhani Karhumäki

Discret. Appl. Math., 2003

Languages Defined by Generalized Equality Sets.

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002

Binary (generalized) Post Correspondence Problem.

Vesa Halava, Tero Harju, Mika Hirvensalo

Theor. Comput. Sci., 2002

Infinite Solutions of Marked Post Correspondence Problem.

Vesa Halava, Tero Harju

Proceedings of the Formal and Natural Computing, 2002

2001

Marked PCP is decidable.

Vesa Halava, Mika Hirvensalo, Ronald de Wolf

Theor. Comput. Sci., 2001

Mortality in Matrix Semigroups.

Vesa Halava, Tero Harju

Am. Math. Mon., 2001

Some New Results on Post Correspondence Problem and Its Modifications.

Vesa Halava, Tero Harju

Bull. EATCS, 2001

An Undecidability Result Concerning Periodic Morphisms.

Vesa Halava, Tero Harju

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000

Periods and Binary Words.

Vesa Halava, Tero Harju, Lucian Ilie

J. Comb. Theory A, 2000

Generalized Post Correspondence Problem for Marked Morphisms.

Vesa Halava, Tero Harju, Mika Hirvensalo

Int. J. Algebra Comput., 2000

1999

Undecidability of the equivalence of finite substitutions on regular language.

Vesa Halava, Tero Harju

RAIRO Theor. Informatics Appl., 1999

Undecidability in Integer Weighted Finite Automata.

Vesa Halava, Tero Harju

Fundam. Informaticae, 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

Languages Accepted by Integer Weighted Finite Automata.

Vesa Halava, Tero Harju

Proceedings of the Jewels are Forever, 1999

1997

On a Geometric Problem of Zigzags.

Vesa Halava, Tero Harju, Lucian Ilie

Inf. Process. Lett., 1997