Publications 2000 - 2005
by Tero Harju

Combinatorics on words, automata
graph theory, combinatorics of DNA

Updated June 2008


My Homepage
    * 2005 *
    Top of Page

  1. Tero Harju, Arto Lepistö, and Dirk Nowotka:
    A characterization of periodicity of bi-infinite words
    Theoret. Comput. Sci. 347 (2005), 419-422.
    doi:10.1016/j.tcs.2004.08.017
  2. Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux:
    Equality sets for recursively enumerable languages
    Theoret. Informatics Appl. 39(4) (2005), 661-675.
    doi:10.1051/ita:2005035
  3. Tero Harju:
    A combinatorial view on gene assembly
    in ''Recent Results in Natural Computing''
    (M. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, eds.)
    Kronos Publishers, Sevilla, 2005, 79-104.
  4. Tero Harju and Dirk Nowotka:
    On the equation xk = z1k1 z2 k2 ¼znkn in a free semigroup
    Theoret. Comput. Sci. 330 (2005), 117-121.
    doi:10.1016/j.tcs.2004.09.012
  5. Tero Harju and Dirk Nowotka:
    Counting bordered and primitive words with a fixed weight
    Theoret. Comput. Sci. 340(2) (2005), 273-279.
    doi:10.1016/j.tcs.2005.03.040
  6. Vesa Halava, Tero Harju, and Michel Latteux:
    Representation of regular languages by equality sets
    Bulletin of the EATCS 86 (2005), 225-228.
  7. Tero Harju, Juhani Karhumäki and Antonio Restivo (eds.):
    Preface for Special issue "Combinatorics on Words"
    Theoret. Comput. Sci. 339(1), 1-165, 2005.
    doi:10.1016/j.tcs.2005.01.002
  8. Vesa Halava, Tero Harju and Michel Latteux:
    Equality sets of prefix morphisms and regular star languages
    Information Proc. Let. 94 (2005), 151-154.
    doi:10.1016/j.ipl.2005.01.014
  9. Tero Harju:
    Combinatorial models of gene assembly
    in ''Proc. Computability in Europe CiE 2005'' (S. B. Cooper, B. Löwe, L. Torenvliet, eds.)
    Lecture Notes in Comput. Sci. 3526 (2005), 188-195.
    doi:10.1007/11494645_23
  10. Tero Harju and Maurice Margenstern:
    Splicing systems for universal Turing machines
    Lecture Notes in Comput. Sci. 3384 (2005), 151-160.
    doi:10.1007/11493785_13
  11. Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux:
    Valence languages generated by equality sets
    J. Automata Lang. Combin. 9 (2004), 399-406.
  12. * 2004 *
    Top of Page

  13. Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott, and Grzegorz Rozenberg:
    ''Computation in Living Cells. Gene Assembly in Ciliates''
    Springer-Verlag, 2004 (201 pages).
    Book on formal models for gene assembly in ciliates.
    See Preface and References
  14. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg:
    Transitivity of local complementation and switching on graphs
    Discrete Math. 278 (2004), 45 - 60.
    doi: 10.1016/j.disc.2003.04.001
  15. Tero Harju, Ion Petre, and Grzegorz Rozenberg:
    Formal properties of gene assembly: equivalence problem for overlap graphs
    Lecture Notes in Comput. Sci. 2950 (Festschrift for Tom Head) (2004), 202 - 212.
    doi:10.1007/b94864
  16. Tero Harju and Dirk Nowotka:
    Periodicity and unbordered words: A proof of Duval's Conjecture
    (STACS'04) Lecture Notes in Comput. Sci. 2996 (2004), 294 - 304.
    doi:10.1007/b96012
  17. Tero Harju:
    Combinatorics on words ps.gz pdf file: pdf
    in Formal Languages and Applications, Series: Studies in Fuzziness and Soft Computing 148
    (C. Martín-Vide, V. Mitrana, Gh. Paun, eds.), Springer-Verlag, 2004, pp. 381 - 392.
  18. Tero Harju, Ion Petre, and Grzegorz Rozenberg:
    Gene assembly in ciliates: Molecular operations
    Bulletin of the EATCS 81 (2003), 236 - 249.
    Also, in Current Trends in Theoretical Computer Science: The Challenge of the New Century (vol. 2)
    (Gh. Paun, G.Rozenberg and A. Salomaa, eds.), World Scientific (2004), 527 - 541 .
    Gene assembly in ciliates: Formal frameworks
    Bulletin of the EATCS 82 (2004), 227 - 241.
    Also, in Current Trends in Theoretical Computer Science: The Challenge of the New Century (vol. 2)
    (Gh. Paun, G.Rozenberg and A. Salomaa, eds.), World Scientific (2004) 543 - 557.
  19. Tero Harju and Dirk Nowotka:
    Minimal Duval extensions
    Internat. J. Foundations of Comput. Sci. 15 (2004), 349 - 354.
    doi: 10.1142/S0129054104002467
  20. Tero Harju and Dirk Nowotka:
    The equation aM = bN cP in a free semigroup (pdf file) pdf
    Semigroup Forum 68 (2004), 488 - 490.
    doi:10.1007/s00233-003-0028-6
  21. Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg:
    Zebra factorizations in free semigroups
    Semigroup Forum 68 (2004), 365 - 372.
    doi:10.1007/s00233-003-0030-z
  22. Vesa Halava and Tero Harju:
    Post Correspondence Problem - recent results
    in Current Trends in Theoretical Computer Science: The Challenge of the New Century (vol. 2)
    (Gh. Paun, G.Rozenberg and A. Salomaa, eds.), World Scientific (2004), 511 - 532.
  23. Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott, and Grzegorz Rozenberg:
    Modelling gene assembly in ciliates
    in Modelling in Molecular Biology (G. Ciobanu, G. Rozenberg eds.)
    Natural Computing Series, Springer-Verlag, 2004, 105 - 124.
  24. Tero Harju and Juhani Karhumäki:
    Many aspects of the defect effect
    Theoret. Comput. Sci. 324(1) (2004), 35 - 54.
    doi:10.1016/j.tcs.2004.03.051
  25. Tero Harju, Ion Petre, and Grzegorz Rozenberg:
    Two models for gene assembly in ciliates
    in Theory Is Forever (J. Karhumäki, H. Maurer, Gh. Paun, G. Rozenberg, eds)
    Lecture Notes in Comput. Sci. 3113, 89 - 101.
    doi:10.1007/b98751
  26. Jurriaan Hage and Tero Harju:
    A characterization of acyclic switching classes using forbidden subgraphs pdf
    SIAM J. Discrete Math. 18(1) (2004), 159 - 176.
    doi: 10.1137/S0895480100381890
  27. Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, and Grzegorz Rozenberg:
    Embedding in switching classes with skew gains pdf
    Proc. Internat. Conference on Graph Transformations (ICGT'04, Rome)
    Lecture Notes in Comput. Sci. 3256 (2004), 257 - 270.
    doi:10.1007/b100934
  28. Tero Harju, Ion Petre, and Grzegorz Rozenberg:
    DNA Computing and Graph Transformation
    Proc. Internat. Conference on Graph Transformations (ICGT'04, Rome)
    Lecture Notes in Comput. Sci. 3256 (2004), 434 - 436.
  29. Vesa Halava and Tero Harju:
    Undecidability in matrices over Laurent polynomials
    Adv. Applied Math. 33 (2004), 747 - 752.
    doi:10.1016/j.aam.2004.04.002
  30. Tero Harju and Dirk Nowotka:
    Border correlation of binary words
    J. Combin. Theory A 108 (2004), 331-341.
    doi:10.1016/j.jcta.2004.07.009
    On-Line Encyclopedia of Integer Sequences:
    1,2,4,7,11,18,29,47,76,121,199,310,521,841,1364,2207,3571, ... Item A091838
    The odd positions seem to be related to the Lucas numbers, but for the even positions we have no interpretation. (The first "exceptional case" is n=12.) -->
  31. * 2003 *
    Top of Page

  32. Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott and Grzegorz Rozenberg:
    Formal systems for gene assembly in ciliates
    in ''Essays dedicated to Jean Berstel'' (P. Seebold, ed.)
    Theoret. Comput. Sci. 292 (2003), 199 - 219.
    doi:10.1016/S0304-3975(01)00223-7
  33. Tero Harju and Dirk Nowotka:
    Periodicity and unbordered segments of words (pdf file) pdf
    Bulletin of the EATCS 80 (2003), 162 - 167.
  34. Tero Harju and Dirk Nowotka:
    About Duval's conjecture
    Proceedings of the DLT'03 (Szeged, Hungary), 2003.
    Lecture Notes in Comput. Sci. 2710 (2003), 316 - 324.
  35. Tero Harju and Grzegorz Rozenberg:
    Computational processes in living cells: gene assembly in ciliates ps pdf file: pdf
    Lecture Notes in Comput. Sci. 2450 (2003), 1 - 20.
  36. Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom and Michel Latteux:
    Languages defined by generalized equality sets
    FCT03 (Malmö, Sweden)
    Lecture Notes in Comput. Sci. 2751 (2003), 355 - 363.
    doi:10.1007/b11926
  37. Tero Harju and Dirk Nowotka:
    On the independence of equations in three variables
    Theoret. Comput. Sci. 307 (2003), 139 - 172.
    doi:10.1016/S0304-3975(03)00098-7
  38. Vesa Halava, Tero Harju and Juhani Karhumäki:
    Decidability of the binary infinite Post Correspondence Problem
    Discrete Appl. Math. 130 (2003), 521 - 526.
    doi:10.1016/S0166-218X(03)00330-5
  39. Jurriaan Hage, Tero Harju and Emo Welzl:
    Euler graphs, triangle-free and bipartite graphs in switching classes
    Fundamenta Informaticae 58 (2003), 23 - 37.
    Earlier versionpdf ICGT'02, October 2002. Lecture Notes in Comput. Sci. 2505 (2002), 148 - 160.
  40. * 2002 *
    Top of Page

  41. Tero Harju:
    Decision questions on integer matrices
    Lecture Notes in Comput. Sci. 2295 (2002), 57 - 68.
    Earlier version: 5th International Conference, DLT 2001, Wien (2001).
  42. Tero Harju, Juhani Karhumäki and Wojtek Plandowski:
    Independent Systems of Equations
    Chapter 13 in M. Lothaire, Algebraic Combinatorics on Words
    (J. Berstel and D. Perrin, eds.), Cambridge University Press, 2002, pages 443 - 472.
  43. Vesa Halava, Tero Harju and Mika Hirvensalo:
    Binary (generalized) Post correspondence problem
    Theoret. Comput. Sci. 276 (2002), 183 - 204.
    doi:10.1016/S0304-3975(01)00157-8
  44. Andrzej Ehrenfeucht, Tero Harju and Grzegorz Rozenberg:
    Gene assembly in ciliates through circular graph decomposition ps.gz
    Theoret. Comput. Sci. 281 (2002), 325 - 349.
    doi:10.1016/S0304-3975(02)00019-1
  45. Vesa Halava and Tero Harju:
    Infinite solutions of marked Post correspondence problem
    Lecture Notes in Comput. Sci. 2300 Festschrift for Grzegorz Rozenberg (2002), 57 - 68.
  46. Vesa Halava and Tero Harju:
    An undecidability result concerning periodic morphisms
    Lecture Notes in Comput. Sci. 2295 (2002), 304 - 310.
    Earlier version: 5th International Conference, DLT 2001, Wien (2001), 314 -- 322.
  47. Tero Harju, Ion Petre and Grzegorz Rozenberg:
    Tutorial on DNA computing and graph transformation -
    computational nature of gene assembly in ciliates
    ,
    Lecture Notes in Comput. Sci. 2505 (2002), 430 - 434.
  48. Andrzej Ehrenfeucht, Tero Harju, Ion Petre and Grzegorz Rozenberg:
    Characterizing the micronuclear gene patterns in ciliates
    Theory of Computation and Systems 35 (2002), 501 - 519.
    doi:10.1007/s00224-002-1043-9
    Earlier version: Lecture Notes in Comput. Sci. 2340 (2002), 279 - 289.
  49. Tero Harju, Oscar Ibarra, Juhani Karhumäki and Arto Salomaa:
    Decision questions in semilinearity and commutation
    J. Comput. System Sci. 65(2) (2002), 278 - 294.
    doi:10.1006/jcss.2002.1836
    Earlier version: ICALP'2001 (Crete), Lecture Notes in Comput. Sci. 2076 (2001), 579 - 590.
  50. Tero Harju and Dirk Nowotka:
    On the density of critical factorizations
    Theoretical Informatics and Applications 36 (2002), 315 - 327.
    doi:10.1051/ita:2002016
  51. * 2001 *
    Top of Page

  52. Tero Harju and Lucian Ilie:
    Forbidden subsequences and permutations sortable on two parallel stacks
    in Where Mathematics, Computer science, Linguistics, and Biology Meet ,
    (C. Martin-Vide and V. Mitrana, eds.), Kluwer, 2001, 267- 275.
  53. Vesa Halava and Tero Harju:
    Some new results on Post Correspondence Problem and its generalizations
    Bulletin of the EATCS 73 (2001), 131 - 141.
  54. Vesa Halava and Tero Harju :
    Mortality in matrix semigroups
    Amer. Math. Monthly 108 (2001), 649 - 653.
  55. * 2000 *
    Top of Page

  56. Vesa Halava, Tero Harju and Lucian Ilie:
    Periods and binary words
    J. Combinat. Theory Ser. A, 89 (2000), 298 - 303.

  57. Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju and Grzegorz Rozenberg :
    Complexity issues in switching of graphs ps.gz
    TAGT'98 (Ehrig, Engels, Kreowski, Rozenberg, eds)
    Lecture Notes in Comput. Sci. 1764 (2000), 59 - 70.
  58. Jurriaan Hage and Tero Harju:
    The size of switching classes with skew gains ps.gz
    Discrete Math. 215 (2000), 81 - 92.
  59. Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju and Grzegorz Rozenberg:
    Pancyclicity in switching classes ps.gz
    Inform. Proc. Lett. 73 (2000), 153 - 156.
  60. Vesa Halava, Tero Harju and Mika Hirvensalo:
    Generalized Post Correspondence Problem for marked morphism
    Internat. J. Algebra Comput. 10 (2000), 757 - 772.
    doi:10.1142/S0218196700000376
  61. Top of Page

    See my
    More recent publications
    previous publications from 1991 - 1999
    My Homepage