Publications
by Tero Harju

Department of Mathematics and Statistics
University of Turku, Finland

Combinatorics on words, automata
graph theory, combinatorics of DNA

Updated 2019

    * 2017-21 *
    Top of Page

  1. Tero Harju:
    A Note on Squares in Binary Words. arXiv

  2. Tero Harju:
    Critical factorisation in square-free words. arXiv

  3. Golnaz Badkobeh, Tero Harju, Pascal Ochem, Matthieu Rosenfeld:
    Avoiding Square-Free Words on Free Groups arXiv

  4. Tero Harju:
    Disposability in Square-Free Words.
    Theoret. Comput. Sci 862 (2021), 155-159.
    doi: 10.1016/j.tcs.2020.07.030
    arXiv

  5. Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov:
    Integer Weighted Automata on Infinite Words.
    DLT 2021, 167-179.

  6. Vesa Halava and Tero Harju:
    On the Steps of Emil Post: from Normal Systems to the Correspondence Decision Problem.
    Acta Cybernetica 24 (2020), 613-623.
    doi: 10.14232/actacyb.284625

  7. Vesa Halava, Tero Harju, Esa Sahla:
    On Shuffling a Word with its Letter-to-Letter Substitution.
    Fundamenta Informaticae 175 (2020), 201-206.
    doi: 10.3233/FI-2020-1954

  8. James Currie, Tero Harju, Pascal Ochem, Narad Rampersad:
    Some further results on squarefree arithmetic progressions in infinite words.
    Theoretical Computer Science 799 (2019), 140-148.
    doi: 10.1016/j.tcs.2019.10.006
    arXiv

  9. Tero Harju:
    On Square-Free Arithmetic Progressions in Infinite Words.
    Theoretical Computer Science 770 (2019), 95-100.
    doi: 10.1016/j.tcs.2018.09.032

  10. Vesa Halava, Tero Harju, Esa Sahla:
    On Fixed Points of Rational Transductions.
    Theoretical Computer Science 732 (2018), 85-88.
    doi: 10.1016/j.tcs.2018.04.030

  11. Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov:
    Weighted automata on infinite words in the context of Attacker-Defender games.
    Information and Computation 255 Part 1 (2017), 27-44.
    doi: 10.1016/j.ic.2017.05.001

  12. Vesa Halava, Tero Harju and Esa Sahla:
    A New Proof for the Undecidability of the Bi-Infinite Post’s Correspondence Problem.
    Fundamenta Informaticae 154 (2017), 167-176
    doi: 10.3233/FI-2017-1558

  13. Vesa Halava and Tero Harju:
    Walks on Tilings of Polygons.
    Theoret. Comput. Sci. 701 (2017), 120 -124.
    doi: 10.1016/j.tcs.2017.02.034

    14. * 2015-2016 *
    Top of Page

  14. Tero Harju, Jetro Vesti, Luca Zamboni:
    On a question of Hof, Knill and Simon on palindromic substitutive systems.
    Monatshefte Math. 179(3), 379-388. Arxiv
    doi: 10.1007/s00605-015-0828-2

  15. Vesa Halava, Tero Harju and Tomi Kärki:
    Similarity relations on words.
    in Combinatorics, Words and Symbolic Dynamics
    (Edited by M. Rigo and V. Berthé)
    Cambridge Univ. Press, 2016, pp. 183-220.

  16. Emilie Charlier, Tero Harju, Svetlana Puzynina, Luca Zamboni:
    Abelian bordered factors and periodicity. Arxiv
    European Journal of Combinatorics 51 (2016), 407-418.
    doi: 10.1016/j.ejc.2015.07.003

  17. Vesa Halava, Tero Harju and Mari Huova:
    On n-permutation Post Correspondence Problem.
    Theoret. Comput. Sci. 601 (2015), 15-20.
    doi: 10.1016/j.tcs.2015.07.021

  18. Vesa Halava, Tero Harju, Reino Niskanen, Igor Potapov:
    Weighted automata on infinite words in the context of Attacker-Defender games. Arxiv
    Lecture Notes in CS (CiE 2015) 9136 (2015), 206-215.
    doi: 10.1007/978-3-319-20028-6_21

  19. Tero Harju, Mari Huova, Luca Zamboni:
    On generating binary words palindromically. Arxiv
    J. Combin. Theory A 129 (2015), 142-159.
    doi: 10.1016/j.jcta.2014.10.003

  20. Tero Harju and Mike Müller:
    Square-free shuffles of words. Arxiv
    Theoret. Comput. Sci. 601 (2015), 29-38.

  21. Tero Harju and Mike Müller:
    A note on short palindromes in square-free words.
    Theoret. Comput. Sci. 562 (2015), 658-659.
    doi:10.1016/j.tcs.2014.10.040

    22. * 2012-14 *
    Top of Page

  22. Tero Harju and Tomi Kärki:
    Minimal Similarity Relations for Square--Free Words.
    Discrete Mathematics and Computer Science (2014), 193-200
    In Memoriam: Alexandru Mateescu.
    Publishing House of the Romanian Academy, Bucharest.

  23. Vesa Halava and Tero Harju:
    Word problem for deterministic and reversible semi-Thue systems.
    Semigroup Forum, 88 (2014) 468-478.
    doi: 10.1007/s00233-013-9550-3

  24. Julien Cassaigne, Vesa Halava, Tero Harju, Francois Nicolas:
    Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More.
    Arxiv

  25. Emilie Charlier, Mike Domaratzki, Tero Harju , and Jeffrey Shallit:
    Composition and Orbits of Language Operations: Finiteness and Upper Bounds.
    Internat. J. Computer Math. 90 (2012), 1171-1196.
    doi: 10.1080/00207160.2012.681305

  26. Vesa Halava and Tero Harju:
    New proof for the undecidability of the Circular PCP.
    Acta Informatica 50 (2013), 331-341.

  27. Tero Harju and Juhani Karhumäki:
    Finite Transducers and Rational Transductions.
    Handbook chapter (2013).

  28. Tero Harju:
    A note on square-free shuffles of words.
    Lecture Notes in CS 8079 (WORDS 2013), 154-160.

  29. Tero Harju:
    Kuratowski closure operations on languages.,
    in Proceedings of RuFiDim II, (Halava, Karhumäki, Matiyasevich, eds.) 2012, pp 5-10.

  30. Tero Harju and Mike Müller:
    Square-free words generated by applying permutations to a prefix.,
    in Proceedings of RuFiDim II, (Halava, Karhumäki, Matiyasevich, eds.) 2012, pp 86-91.

  31. Robert Brijder, Mark Daley, Tero Harju, Natasha Jonoska, Ion Petre and Grzegorz Rozenberg:
    Computational gene assembly in ciliates.,
    in Handbook of Natural Computing,Vol II (Th.Bäck, J.Kok and G.Rozenberg, eds.) 2012, pp 1233-1280.
    see Springer page

  32. Tero Harju :
    Square-free words obtained from prefixes by permutations.
    Theoret. Comput. Sci. 429 (2012), 128-133.
    doi: 10.1016/j.tcs.2011.12.031

  33. Emilie Charlier, Mike Domaratzki, Tero Harju , and Jeffrey Shallit:
    Composition and Orbits of Language Operations: Finiteness and Upper Bounds.
    Internat. J. Computer Math. 90 (2012), 1171-1196.
    doi: 10.1080/00207160.2012.681305

  34. Robert Brijder, Tero Harju, and Hendrik Jan Hoogeboom:
    Pivots, determinants, and perfect matchings of graphs.
    Theoret. Comput. Sci. 454 (2012), 64-71.

  35. Sepinoud Azimi, Tero Harju , Miika Langille, and Ion Petre:
    Simple gene assembly as a rewriting of directed overlap-inclusion graphs.
    Theoret. Comput. Sci 454 (2012), 30-37.
    doi: 10.1016/j.tcs.2012.04.018

    36. * 2009-11 *
    Top of Page

  36. Emilie Charlier, Mike Domaratzki, Tero Harju and Jeffrey Shallit:
    Finite orbits of language operations. ArXiv
    Lecture Notes in CS 6638 (LATA 2011), 204-215.
    doi: 10.1007/978-3-642-21254-3_15

  37. Tero Harju , Tomi Kärki and Dirk Nowotka :
    The number of positions starting a square in binary words.
    Electronic J. Combin. 18(1) (2011) paper 6. Web page

  38. Tero Harju and Tomi Kärki:
    On the number of frames in binary words.
    Theoret. Comput. Sci, 412, 5276-5284.
    doi: 10.1016/j.tcs.2011.05.032

  39. Sepinoud Azimi, Tero Harju , Miika Langille, Vladimir Rogojin and Ion Petre:
    Directed overlap-inclusion graphs as representations of ciliate genes.
    Fundamenta Inf. 110 (2011), 29-44.

  40. Vesa Halava, Tero Harju and Tomi Kärki:
    A new proof for the decidability of D0L ultimate periodicity. Arxiv
    EPTCS 63: Proc. WORDS'2011, 147-152.

  41. Tero Harju:
    Square-free walks on labelled graphs. ArXiv .

  42. Volker Diekert, Tero Harju and Dirk Nowotka:
    Weinbaum factorizations of primitive words. (Russian) (in English):
    Izvestiya Vuzov. Matematika 2010 (1), 21-33.
    In English: Russian Mathematics (Iz VUZ) 54 (1), 16-25.
    doi: 10.3103/S1066369X10010032

  43. Vesa Halava, Tero Harju and Tomi Kärki:
    On the number of squares in partial words.
    RAIRO Theoret. Inf. Applic. 44 (2010), 125-138.
    doi: 10.1051/ita/2010008

  44. Vesa Halava, Tero Harju, Tomi Kärki and Michel Rigo:
    On the periodicity of morphic words.
    Lecture Notes in CS 6224 (DLT, London, Ontario 2010) , 209-217
    doi: 10.1007/978-3-642-14455-4_20

  45. Tero Harju and Dirk Nowotka:
    Cyclically repetition-free words on small alphabets.
    Inf. Processing Letters 110 (2010), 591-595.
    doi: 10.1016/j.ipl.2010.05.005

  46. Tero Harju:
    Weinbaum factorizations (Abstract).
    Oberwolfach Report No. 37/2010 2010 (1), 2212-2213.
    Mini-Workshop: Combinatorics on Words
    (edited by V. Berthe, J. Karhumäki, D. Nowotka, J. Shallit)
    doi: 10.4171/OWR/2010/37

  47. Vesa Halava, Tero Harju, Tomi Kärki, and Patrice Seebold:
    Overlap-freeness in infinite partial words.
    Theoret. Comput. Sci. 410 (2009), 943-948.
    doi:10.1016/j.tcs.2008.12.041

  48. Vesa Halava, Tero Harju and Tomi Kärki:
    The theorem of Fine and Wilf for relational periods.
    Theoret. Inf. Applic. (RAIRO) 43 (2009), 209-220.
    doi:10.1051/ita:2008025

  49. Jurriaan Hage and Tero Harju:
    On involutions arising from graphs.
    in Algorithmic Bioprocesses Springer Series: Natural Computing Series.
    Condon, A.; Harel, D.; Kok, J.N.; Salomaa, A.; Winfree, E. (Eds.) 2009, pp. 623-630.
    see Springer page

  50. Tero Harju:
    Post Correspondence Problem and small dimensional matrices.
    Lecture Notes in CS 5583 (2009), 39-46.
    doi:10.1007/978-3-642-02737-6_3

  51. Tero Harju, Alexander Okhotin, Grzegorz Rozenberg and Arto Salomaa (Eds):
    A bird's eye view of theory.
    Special issue of Theoret. Comput. Sci. 410 (30-32), 2009.

    * 2008 *
    Top of Page

  52. Vesa Halava, Tero Harju and Tomi Kärki:
    Interaction properties of relational words.
    Discrete Math. Theoret. Comput. Sci. 10 (2008), 87-112.

  53. Jean-Pierre Duval, Tero Harju, and Dirk Nowotka:
    Unbordered factors and Lyndon words.
    Discrete Math. 308 (2008) 2261– 2264.
    doi:10.1016/j.disc.2006.09.054

  54. Vesa Halava, Tero Harju and Tomi Kärki:
    Defect theorems with compatibility relations. Preliminary version
    doi: 10.1007/s00233-007-9013-9
    Semigroup Forum 76 (2008) 1-24.

  55. Tero Harju and Juhani Karhumäki (eds.):
    Special issue for Developments in Language Theory (DLT 2007).
    Internat. J. Found. Comput. Sci. 19(3) (2008), 495-690.

  56. Jean Berstel, Tero Harju and Juhani Karhumäki (eds.):
    Special issue for Fibonacci Words.
    Theoret. Informatics Applic. (RAIRO) 42(4) (2008), 657-762.

  57. Tero Harju, Chang Li and Ion Petre:
    Parallel complexity of signed graphs for gene assembly in ciliates.
    Soft Comp. 12 (2008), 731-737.
    doi:10.1007/s00500-007-0233-4

  58. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki:
    Post Correspondence Problem for short words.
    Informat. Process. Letters 108 (2008), 115-118.
    doi:10.1016/j.ipl.2008.04.013

  59. Tero Harju, Ion Petre, Vladimir Rogojin, and Grzegorz Rozenberg:
    Patterns of simple operations for gene assembly.
    Discrete Appl. Math. 156 (2008), 2581-2597.
    doi:10.1016/j.dam.2007.09.026

  60. Vesa Halava, Tero Harju and Tomi Kärki:
    Square free partial words.
    Information Processing Letters 108 (2008), 290-292.
    doi:10.1016/j.ipl.2008.06.001

  61. Tero Harju, Chang Li and Ion Petre:
    Graph theoretic approach to parallel gene assembly.
    Discrete Appl. Math. 156 (2008), 3416-3429.
    doi: 10.1016/j.dam.2008.01.022

  62. Tero Harju and Dirk Nowotka:
    Bordered conjugates of words over large alphabets.
    Electronic J. Combin. 15(1) (2008), N41. Combinatorics.org

  63. Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, and Igor Potapov:
    Matrix equations and Hilbert’s tenth problem.
    Internat. J. Algebra and Computation 18 (2008), 1231-1241.

    64. * 2007 *
    Top of Page

  64. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg:
    Finite metrics in switching classes.
    An older version:
    Discrete Appl. Math., 155 (2007), 68-73.
    doi:10.1016/j.dam.2006.04.041

  65. Vesa Halava, Tero Harju, and Juhani Karhumäki:
    Structure of infinite solutions of marked and binary
    Post Correspondence problems.
    Theory of Comp. Syst. 40 (2007), 43-54.
    doi:10.1007/s00224-005-1222-6
    Older version: Characterization of infinite solutions
    of marked and binary Post Correspondence problems

  66. Tero Harju, Chang Li, Ion Petre and Grzegorz Rozenberg:
    Complexity measures for gene assembly.
    Lecture Notes in Comput. Sci. 4366 (2007), 42-60.

  67. Vesa Halava, Tero Harju, Juhani Karhumäki, and Michel Latteux:
    Extensions of the decidability of the marked PCP to instances with unique blocks.
    Theoret. Comput. Sci. 380 (2007), 355-362.

  68. Tero Harju, and Dirk Nowotka:
    Periodicity and unbordered words: a proof of the extended Duval conjecture.
    J. Assoc. Comput. Mach. 54(4) (July 2007).

  69. Tero Harju, Juhani Karhumäki, and Arto Lepistö (eds):
    Proceedings of the 11th DLT.
    Lecture Notes Comput. Sci. 4588 (2007). Contents (Springer)
    Online link (Springer)

  70. Vesa Halava, Tero Harju and Mika Hirvensalo:
    Undecidability bounds for integer matrices using Claus instances.
    Internat. J. Found. Comput. Sci. 18 (2007), 931-948.

  71. Vesa Halava, Tero Harju, Tomi Kärki and Luca Zamboni:
    Relational Fine and Wilf words.
    Proceedings of WORDS'07 (Marseille).

  72. Vesa Halava, Tero Harju and Tomi Kärki:
    Relational codes of words.
    Theoret. Comput. Sci. 389 (2007), 237–249.

  73. Vesa Halava and Tero Harju:
    On Markov's undecidability theorem for integer matrices.
    Semigroup Forum 75 (2007), 173-80.

  74. Jurriaan Hage and Tero Harju:
    Towards a characterization of bipartite switching classes
    by means of forbidden subgraphs.     pdf file:
    Discussiones Mathematicae Graph Theory 23 (2007) 471-483.

    75. * 2006 *
    Top of Page

  75. Tero Harju, Ion Petre, and Grzegorz Rozenberg:
    Modelling simple operations for gene assembly.
    in "Nanotechnology: Science and Computation" (Chen, J., Jonoska, N., Rozenberg, G. eds.)
    Springer-Verlag 2006, 361-376.

  76. Vesa Halava, Tero Harju, and Mika Hirvensalo:
    Positivity of second order linear recurrent sequences.
    Discrete Applied Math. 154 (2006), 447-451.

  77. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg:
    Embedding linear orders in grids.
    Acta Informatica 42 (2006), 419-428.
    doi:10.1007/s00236-005-0001-9

  78. Vesa Halava, Tero Harju, and Juhani Karhumäki:
    Undecidability in omega-regular languages.
    Fundamenta Inf. 73 (2006), 119-125.

  79. Tero Harju and Dirk Nowotka:
    On unique factorizations of primitive words.
    Theoret. Comput. Sci. (2006) 356, 186-189.
    doi:10.1016/j.tcs.2006.01.031

  80. Tero Harju:
    Characterizations of regularity.
    Lecture Notes in Artificial Int. 4002 (2006) 1-8.

  81. Tero Harju and Dirk Nowotka:
    Binary words with few squares.
    Bulletin of the EATCS 89 (2006), 164-166.

  82. Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, and Grzegorz Rozenberg:
    The embedding problem for switching classes of graphs.
    Fundamenta Inf. 74 (2006), 115-134.

  83. Tero Harju, Chang Li, Ion Petre, and Grzegorz Rozenberg:
    Parallelism in gene assembly.
    Natural Computing - an International Journal 5 (2006), 203-223.
    doi:10.1007/s11047-005-4462-0
    Short version: Lecture Notes in Comput. Sci. 3384 (2005), 140-150.
    doi:10.1007/11493785_12

  84. Tero Harju, Ion Petre, Vladimir Rogojin, and Grzegorz Rozenberg:
    Simple operations for gene assembly.
    Lecture Notes in Comput. Sci. 3892 (2006), 96-111.
    doi:10.1007/11753681_8
    Previous version: Preproceedings of the DNA11, June (2005).

  85. Tero Harju and Dirk Nowotka:
    Periods in extensions of words.
    Acta Inf. 43 (2006), 165-171.
    doi:10.1007/s00236-006-0014-z

  86. Vesa Halava and Tero Harju:
    Undecidability of infinite Post Correspondence Problem for instances of size 9.
    Theory Inform. Appl. 40 (2006) 551-557.
    doi:10.1051/ita:2006039

    87. * Forthcoming *
    Top of Page

  87. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki:
    Skolem's Problem - On the border between decidability and undecidability.
    TUCS report TR683.pdf
    submitted.

** Top of Page

My Homepage