Tero Harju

Publications (March 2020)

Co-authors

Azimi Sepinoud

Bell Paul

Berstel Jean

Brijder Robert

Cassaigne Julien

Charlier

Emilie

Choffrut Cristian

Culik II Karel

Currie James

Daley Mark

Diekert Volker

Domaratzki Mike

Duval Jean-Pierre

Ehrenfeucht Andrzej

Engelfriet Joost

Ernvall Mari

Hage Jurriaan

Halava Vesa

Hirvensalo Mika

Honkala Iiro

Hoogeboom Hendrik Jan

Huova Mari

Ibarra Oscar

Ilie Lucian

Jonoska Natasha

arki Tomi

Karhum

aki Juhani

Keesmaat Niko

Kleijn Jetty

Krob Daniel

Langille Miika

Latteux Michel

Lepist

o Arto

Linna Matti

Lipponen Marjo

Li Chang

uller Mike

Margenstern Maurice

Mateescu Alexandru

Nicolas Francois

Niskanen Reino

Nowotka Dirk

Ochem Pascal

Okhotin Alexander

Penttonen Martti

Petre Ion

Petrich Mario

Plandowski Wojtek

Potapov Igor

Prescott David M.

Proskurowski Andrzej

Puzynina Svetlana

Rampersad Narad

Restivo Antonio

Rigo Michel

Rogojin Vladimir

Rozenberg Grzegorz

ebold Patrice

Sahla Esa

Salomaa Arto

Shallit Jeffrey

Terlutte Alan

Vesti Jetro

Welzl Emo

Zamboni Luca Q.

ten Pas Paulien

Tero Harju (2020) 2

[1] T. HARJU, A polynomial recognition algorithm for the EDTOL languages, Elektron. Informa-

tionsverarb. Kybernet., EIK 13 (1977), 169 – 177.

(A) Peer-reviewed scientiﬁc articles

[2] T. HARJU, A simulation result for auxiliary pushdown automata, J. Comput. Syst. Sci. 19

(1979), 119 – 132. https://doi.org/10.1016/0022-0000(79)90023-0

[3] T. HARJU and M. PENTTONEN, Some decidability problems of sentential forms, Internat. J.

Computer Math. 7 (1979), 95 – 107. https://doi.org/10.1080/00207167908803161

[4] K. CULIK II and T. HARJU, The ω-sequence equivalence problem for DOL systems is de-

cidable, Proc. 13th Annual ACM Symp. on Theory of Comput. (ACM’81, Milwaukee, USA),

(1981), 1 – 6.

[5] K. CULIK II and T. HARJU, Dominoes over a free monoid, Theoret. Comput. Sci. 18 (1982),

279 – 300. https://doi.org/10.1016/0304-3975(82)90070-6

[6] T. HARJU, A note on inﬁnite words obtained by iterating morphisms, Bull. Eur. Assoc. Theor.

Comput. Sci. 19 (1982), 12 – 16.

[7] T. HARJU, On repetition free morphisms, Bull. Eur. Assoc. Theor. Comput. Sci. 19 (1983),

18 – 20.

[8] K. CULIK II and T. HARJU, The ω-sequence problem for DOL systems is decidable,

J. Assoc. Comput. Mach. 31 (1984), 282 – 298. https://doi.org/10.1145/62.2161

[9] T. HARJU and M. LINNA, The equation h(w) = w

in binary alphabets, Theoret. Comput. Sci.

33 (1984), 327 – 329. https://doi.org/10.1016/0304-3975(84)90093-8

[10] T. HARJU, On factorizations of words, Bull. Eur. Assoc. Theor. Comput. Sci. 24 (1984), 217.

[11] T. HARJU, P67: A solution to a problem of Karhum

aki, Bull. Eur. Assoc. Theor. Comput. Sci.

24 (1984), 218 – 220.

[12] T. HARJU, On ﬁnitely based dominions in semigroups, Ann. Univ. Turkuensis Ser. 186 (1984),

7 – 11.

[13] T. HARJU, On cyclically overlap-free words in binary alphabets, in The Book of L (G. Rozen-

berg and A. Salomaa, eds.), Springer-Verlag, 1985, 123 – 130. https://doi.org/10.1007/

978-3-642-95486-3 10

[14] T. HARJU and M. LINNA, On the periodicity of morphisms on free monoids, RAIRO Inform.

eorique Appl. 20 (1986), 47 – 54. http://eudml.org/doc/92245

[15] T. HARJU, J. KARHUM

AKI and H.C.M. KLEIJN, On morphic generation of regular languages,

Discrete Appl. Math. 15 (1986), 55 – 60. https://doi.org/10.1016/0166-218X(86)90018-1

[16] T. HARJU and J. KARHUM

AKI, On the defect theorem and simpliﬁability, Semigroup Forum

33 (1986), 199 – 217. https://doi.org/10.1007/BF02573193

Tero Harju (2020) 3

[17] T. HARJU, Ehrenfeuchtin otaksuma ja sen ratkaisu (extended abstract),

Matemaatikkop

aiv

at Turussa 1986 (R. Ernvall, Ed.), 21 – 23 (in Finnish).

[18] T. HARJU and H.C.M. KLEIJN, Cardinality problems of compositions of morphisms and

inverse morphisms, Math. System Theory 22 (1989), 151 – 159. https://doi.org/10.1007/

BF02088295

[19] K. CULIK II and T. HARJU, Dominoes and the regularity of DNA splicing languages, 16th

Internat. Colloq. Automata, Languages and Programming (ICALP’89, Stresa, Italy), Lecture

Notes in Comput. Sci. 372 (1989), 222 – 233. https://doi.org/10.1007/BFb0035763

[20] T. HARJU and J. KARHUM

AKI, Decidability of the multiplicity equivalence of multitape ﬁnite

automata, Proc. 22nd ACM Symp. on Theory of Comput. (ACM’90, Baltimore, USA) (1990),

477 – 481.

[21] T. HARJU and H.C.M. KLEIJN, Decidability problems for unary output sequential transducers,

Discrete Appl. Math. 32 (1991), 131 – 139. https://doi.org/10.1016/0166-218X(91)90096-F

[22] K. CULIK II and T. HARJU, Splicing semigroups of dominoes and DNA, Discrete Appl. Math.

31 (1991), 261 – 277. https://doi.org/10.1016/0166-218X(91)90054-Z

[23] T. HARJU and J. KARHUM

AKI, The equivalence problem of multitape ﬁnite automata, Theoret.

Comput. Sci. 78 (1991), 347 – 355. https://doi.org/10.1016/0304-3975(91)90356-7

[24] T. HARJU, H.C.M. KLEIJN, and M. LATTEUX, Compositional representation of rational func-

tions, RAIRO Inform. Th

eorique et Appl. 26 (1992), 243 – 255. http://www.numdam.org/item/

ITA 1992 26 3 243 0

[25] T. HARJU, H.C.M. KLEIJN, and M. LATTEUX, Deterministic sequential functions, Acta Infor-

mat. 29 (1992), 545 – 554. https://doi.org/10.1007/BF01185560 %

[26] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Permutable transformation semigroups,

Semigroup Forum 47 (1993), 123 – 125. https://doi.org/10.1007/BF02573748

[27] T. HARJU and H.C.M. KLEIJN, Morphisms and rational transducers, Column in Formal Lan-

guage Theory (A. Salomaa, ed.) Bull. Eur. Assoc. Theor. Comput. Sci. 51 (1993), 168 – 180.

[28] T. HARJU and G. ROZENBERG, Reductions for primitive 2-structures, Fundamenta Informat.

20 (1994), 133 – 144. https://doi.org/10.3233/FI-1994-201235

[29] T. HARJU, N.W. KEESMAAT, and H.C.M. KLEIJN, The intersection problem for alphabetic

vector monoids, RAIRO Inform. Th

eorique et Appl. 28 (1994), 295 – 301. https://doi.org/10.

1051/ita/1994283-402951

[30] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Incremental construction of 2-structures,

Discrete Math. 128 (1994), 113 – 141. https://doi.org/10.1016/0012-365X(94)90107-4

[31] T. HARJU, H.C.M. KLEIJN, M. LATTEUX, and A. TERLUTTE, Representation of rational

functions with preﬁx and sufﬁx codings, Theoret. Comput. Sci. 134 (1994), 403 – 414.

https://doi.org/10.1016/0304-3975(94)90245-3

Tero Harju (2020) 4

[32] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Quotients and plane trees of group la-

beled 2-structures, in Proc. Graph Grammars and Their Applications to Computer Science

(GraGra’94, Williamsburg, USA) (1994), 247 – 251.

[33] T. HARJU, H.J. HOOGEBOOM, and H.C.M. KLEIJN, Identities and transductions, Lecture

Notes in Comput. Sci. 812 (1994), 140 – 144. https://doi.org/10.1007/3-540-58131-6 43

[34] T. HARJU and G. ROZENBERG, Decomposition of inﬁnite labeled 2-structures, Lecture Notes

in Comput. Sci. 812 (1994), 145 – 158. https://doi.org/10.1007/3-540-58131-6 44

[35] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Theory of 2-structures, 24th Internat.

Colloq. Automata, Languages and Programming (ICALP’95, Szeged, Hungary), Lecture Notes

in Comput. Sci. 841 (1995), 1 – 14 . https://doi.org/10.1007/3-540-60084-1 58

[36] T. HARJU, J. KARHUM

AKI, and W. PLANDOWSKI, Compactness of systems of equations

in semigroups, 24th Internat. Colloq. Automata, Languages and Programming (ICALP’95,

Szeged, Hungary), Lecture Notes in Comput. Sci. 841 (1995), 443 – 452. https://doi.org/10.

1007/3-540-60084-1 95

[37] J. ENGELFRIET, T. HARJU, A. PROSKUROWSKI, and G. ROZENBERG, Characterization and

complexity of uniformly nonprimitive labeled 2-structures, Theoret. Comput. Sci. 154 (1996),

247 – 282. https://doi.org/10.1016/0304-3975(94)00272-X

[38] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Group based graph transformations and

hierarchical representations of graphs, Proc. 5th Int. Workshop on Graph Grammars and their

Application to Computer Science (J. Cuny et al., eds.), Lecture Notes in Comput. Sci. 1073

(1996), 502 - 520. https://doi.org/10.1007/3-540-61228-9 108

[39] T. HARJU, M. LIPPONEN, and A. MATEESCU, Flatwords and Post Correspondence problem,

Theoret. Comput. Sci. 161 (1996), 93 – 108. https://doi.org/10.1016/0304-3975(95)00092-5

[40] T. HARJU, J. KARHUM

AKI, and D. KROB, Remarks on generalized Post Correspondence

problem, 13th Annual Symp. Theoret. Aspects of Computer Science (STACS’96, Greno-

ble, France), Lecture Notes in Comput. Sci. 1046 (1996), 39 – 48. https://doi.org/10.1007/

3-540-60922-9 4

[41] V. HALAVA, T. HARJU, and L. ILIE, A geometric problem of zigzags. Inform. Process. Lett.

62 (1997), 1 – 4. https://doi.org/10.1016/S0020-0190(97)00042-2

[42] T. HARJU, J. KARHUM

AKI, and W. PLANDOWSKI, Compactness of systems of equations

in semigroups, Internat. J. Algebra Comput. 7 (1997), 457 – 470. https://doi.org/10.1007/

3-540-63246-8

[43] C. CHOFFRUT, T. HARJU, and J. KARHUM

AKI, A note on decidability questions on presenta-

tions of word semigroups, Theoret. Comput. Sci. 183 (1997), 83 – 92. https://doi.org/10.1016/

S0304-3975(96)00311-8

Tero Harju (2020) 5

[44] T. HARJU, J. KARHUM

AKI, and M. PETRICH, Compactness of systems of equations on

completely regular semigroups, Structures in logic and computer science (J. Mycielski et

al., eds.), Lecture Notes in Comput. Sci. 1261 (1997), 268 – 280. https://doi.org/10.1007/

3-540-63246-8 16

[45] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Invariants of inversive 2-structures on

groups of labels, Math. Structures Comput. Sci. 7 (1997), 303 – 327. https://doi.org/10.1017/

S0960129597002260

[46] T. HARJU and L. ILIE, Languages obtained from inﬁnite words, RAIRO Inform. Th

eorique

Appl. 31 (1997), 445 – 455.

[47] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, 2-Structures – A Framework for Decom-

position and Transformation of Graphs, Chapter 6 in Handbook of Graph Grammars and Com-

puting by Graph Transformations, Vol. I. Foundations (G. Rozenberg, ed.), World Scientiﬁc,

1997, pp. 401 – 478.

[48] T. HARJU and J. KARHUM

AKI, Morphisms, Chapter 7 in Handbook of Formal Languages, Vol

1. Word, Language, Grammar (G. Rozenberg and A. Salomaa, eds.), Springer-Verlag, 1997, pp.

439 – 510. https://doi.org/10.1007/978-3-642-59136-5 7

[49] J. HAGE and T. HARJU, Acyclicity of switching classes. European J. Combin. 19 (1998), 321 –

327. https://doi.org/10.1006/eujc.1997.0191

[50] T. HARJU and L. ILIE, On quasi orders of words and the conﬂuence property, Theoret. Comput.

Sci. 200 (1998), 205 – 224. https://doi.org/10.1016/S0304-3975(97)00259-4

[51] A. EHRENFEUCHT, T. HARJU, P. TEN PAS, and G. ROZENBERG, Permutations, parenthesis

words, and Schr

oder numbers, Discrete Math. 190 (1998), 259 – 264. https://doi.org/10.1016/

S0012-365X(98)00155-1

[52] T. HARJU, A. MATEESCU, and A. SALOMAA, Shufﬂe on trajectories: the Sch

utzenberger

product and related operations, 23rd Internat. Symposium Math. Foundations Computer Sci-

ence (MFCS’98, Brno 1998; L. Brim et al., eds.), Lecture Notes in Comput. Sci. 1450 (1998),

503 – 511. https://doi.org/10.1007/BFb0055800

[53] V. HALAVA and T. HARJU, Undecidability in integer weighted ﬁnite automata, Fundamenta

Informat. 38 (1999), 189 – 200. https://doi.org/10.3233/FI-1999-381215

[54] V. HALAVA and T. HARJU, Undecidability of the equivalence of ﬁnite substitutions on reg-

ular languages, Theoret. Informatics Appl. 33 (1999), 117 – 124. https://doi.org/10.1051/ita:

1999109

[55] J. CASSAIGNE, T. HARJU, and J. KARHUM

AKI, On the decidability of the freeness of ma-

trix semigroups, Internat. J. Algebra Comput. 9 (1999), 295 – 305. https://doi.org/10.1142/

S0218196799000199

Tero Harju (2020) 6

[56] T. HARJU, V. HALAVA, and M. HIRVENSALO, Generalized PCP is decidable for marked

morphisms, Proc. Internat. Symp. on Foundations in Computer Science (FCT’99, Iasi, Ro-

mania; G. Ciobanu et al., eds.), Lecture Notes in Comput. Sci. 1684 (1999), 304 – 315.

https://doi.org/10.1007/3-540-48321-7 25

[57] V. HALAVA and T. HARJU, Languages accepted by integer weighted ﬁnite automata, in Jewels

are Forever (J. Karhum

aki et al., eds), Springer-Verlag, 1999, pp.123 – 134. https://doi.org/10.

1007/978-3-642-60207-8 11

[58] T. HARJU, Switching of directed graphs, Proc. 7th Nordic Combinatorial Conference (T. Harju

and I. Honkala, Eds.), 1999, 31 – 37.

[59] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, The Theory of 2-Structures.

A Framework for Decomposition and Transformation of Graphs, World Scientiﬁc, 1999, xvi +

291 pages.

[60] T. HARJU and I. HONKALA (eds.), Proceedings of the 7th Nordic Combinatorial Conference,

Painosalama, Turku 1999, ii + 85 pages.

[61] V. HALAVA, T. HARJU, and L. ILIE, Periods and binary words, J. Combin. Theory Ser.A 89

(2000), 298 – 303. https://doi.org/10.1006/jcta.1999.3014

[62] A. EHRENFEUCHT, J. HAGE, T. HARJU, and G. ROZENBERG, Complexity issues in switching

classes, Theory and Application of Graph Transformations, TAGT’98 (H. Ehrig et al., eds.),

Lecture Notes in Comput. Sci. 1764 (2000), 59 – 70.

[63] J. HAGE and T. HARJU, The size of switching classes with skew gains, Discrete Math. 215

(2000), 81 – 92. https://doi.org/10.1016/S0012-365X(99)00243-5

[64] A. EHRENFEUCHT, J. HAGE, T. HARJU, and G. ROZENBERG, Pancyclicity in switching

classes, Inform. Process. Lett. 73 (2000), 153 – 156. https://doi.org/10.1016/S0020-0190(00)

00020-X

[65] V. HALAVA, T. HARJU, and M. HIRVENSALO, Generalized Post Correspondence Problem for

marked morphisms, Internat. J. Algebra Comput. 10 (2000), 757 – 772. https://doi.org/10.1142/

S0218196700000376

[66] V. HALAVA and T. HARJU, Mortality in matrix semigroups, Amer. Math. Monthly 108 (2001),

649 – 653. https://doi.org/10.2307/2695274

[67] T. HARJU and L. 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 Acad. Publ., Dordrecht, 2001, 267 – 275. https://doi.org/10.

1007/978-94-015-9634-3 24

[68] T. HARJU, O. IBARRA, J. KARHUM

AKI, and A. SALOMAA, Decision questions concern-

ing semilinearity, morphisms and commutation of languages, 28th Internat. Colloq. Au-

tomata, Languages and Programming (ICALP’01, Crete, Greece; F. Orejas, P. G. Spirakis,

Tero Harju (2020) 7

J. van Leeuwen, eds.), Lecture Notes in Comput. Sci. 2076 (2001), 579 – 590. https://doi.org/

10.1007/3-540-48224-5 48

[69] V. HALAVA and T. HARJU, Some new results on Post Correspondence Problem and its gen-

eralizations, Column in Formal Language Theory (A. Salomaa, ed.) Bull. Eur. Assoc. Theor.

Comput. Sci. 73 (2001), 131 – 141.

[70] T. HARJU, I. PETRE, and G. ROZENBERG, Tutorial on DNA computing and graph transfor-

mation – Computational nature of gene assembly in ciliates, Internat. Conference on Graph

Transformations (ICGT’02, Barcelona; A. Corradini et al., Eds.), Lecture Notes in Comput.

Sci. 2505 (2002), 430 – 434. https://doi.org/10.1007/3-540-45832-8 31

[71] V. HALAVA, T. HARJU, and M. HIRVENSALO, Binary (generalized) Post Correspondence

Problem, Theoret. Comput. Sci. 276 (2002), 183 – 204. https://doi.org/10.1016/S0304-3975(01)

00157-8

[72] V. HALAVA and T. HARJU, An undecidability result concerning periodic morphisms, Proc.

5th Internat. Conf. on Developments in Language Theory (DLT 2001, Wien), Lecture Notes in

Comput. Sci. 2295 (2002), 304 – 310. https://doi.org/10.1007/3-540-46011-X 26

[73] A. EHRENFEUCHT, T. HARJU and G. ROZENBERG, Gene assembly through cyclic graph

decomposition, Theoret. Comput. Sci. 281 (2002), 325 – 349. https://doi.org/10.1016/

S0304-3975(02)00019-1

[74] V. HALAVA, T. HARJU, M. HIRVENSALO, and J. KARHUM

AKI, (G)PCP for words of length

two (extended abstract), Proceedings of 9-

eme Conf

erence Internat. Journ

ees Montoises

d’Informatique Th

eorique, 2002, 6 pages.

[75] A. EHRENFEUCHT, T. HARJU, I. PETRE, and G. ROZENBERG, Characterizing the micronu-

clear gene patterns in ciliates, Theory of Comput. Syst. 35 (2002), 501 – 519. https://doi.org/10.

1007/s00224-002-1043-9

[76] T. HARJU, O. IBARRA, J. KARHUM

AKI, and A. SALOMAA, Some decision problems con-

cerning semilinearity and commutatio, J. Comput. Syst. Sci. 65 (2002), 278 – 294. https:

//doi.org/10.1006/jcss.2002.1836

[77] T. HARJU and D. NOWOTKA, Density of critical factorizations, Theoret. Informatics Appl. 36

(2002), 315 – 327. https://doi.org/10.1051/ita:2002016

[78] T. HARJU, Decision questions on integer matrices, Proc. 5th Internat. Conf. on Developments

in Language Theory (DLT 2001, Wien), Lecture Notes in Comput. Sci. 2295 (2002), 57 – 68.

https://doi.org/10.1007/3-540-46011-X 5

[79] J. HAGE, T. HARJU, and E. WELZL, Euler graphs, triangle-free graphs and bipartite graphs

in switching classes, Internat. Conference on Graph Transformations (ICGT’02, Barcelona;

A. Corradini et al., eds.), Lecture Notes in Comput. Sci. 2505 (2002), 148 – 160. https://doi.org/

10.1007/3-540-45832-8 13

Tero Harju (2020) 8

[80] V. HALAVA and T. HARJU, Inﬁnite solutions of marked Post Correspondence Problem, in For-

mal and Natural Computing. Essays dedicated to Grzegorz Rozenberg (W. Brauer et al., eds),

Lecture Notes in Comput. Sci. 2300 (2002), 57 – 68. https://doi.org/10.1007/3-540-45711-9 4

[81] T. HARJU, J. KARHUM

AKI, and W. PLANDOWSKI, Independent Systems of Equations,

Chapter 14 in M. Lothaire, Algebraic Combinatorics of Words (J. Berstel and D. Perrin, eds.),

Cambridge University Press, 2002, pp. 443 – 472.

[82] A. EHRENFEUCHT, T. HARJU, I. PETRE, D.M. PRESCOTT, and G. ROZENBERG, Formal sys-

tems for gene assembly in ciliates, Theoret. Comput. Sci. 292 (2003), 199 – 219. https:

//doi.org/10.1016/S0304-3975(01)00223-7

[83] T. HARJU and D. NOWOTKA, About Duval’s conjecture, Proc. 7th International Conference

on Developments in Language Theory (DLT’03, Szeged, Hungary), Lecture Notes in Comput.

Sci. 2710 (2003), 316 – 324. https://doi.org/10.1007/3-540-45007-6 25

[84] T. HARJU and G. ROZENBERG, Computational processes in living cells: gene assembly in

ciliates, Developments in Language Theory (DLT 2002, Kioto; M. Ito and M. Toyama, eds.),

Lecture Notes in Comput. Sci. 2450 (2003), 1 – 20. https://doi.org/10.1007/3-540-45005-X 1

[85] V. HALAVA, T. HARJU, H.J. HOOGEBOOM, and M. LATTEUX, Languages deﬁned by gener-

alized equality sets, 14th Internat. Symp. on Fundamentals of Computation Theory (FCT’03,

Malm

o, Sweden, 2003; A. Lingas and B. J. Nilsson, eds.), Lecture Notes in Comput. Sci. 2751

(2003), 355 – 363. https://doi.org/10.1007/978-3-540-45077-1 33

[86] T. HARJU and D. NOWOTKA, On the independence of equations in three variables, Theoret.

Comput. Sci. 307 (2003), 139 – 172. https://doi.org/10.1016/S0304-3975(03)00098-7

[87] V. HALAVA, T. HARJU, and J. KARHUM

AKI, Decidability of the binary inﬁnite Post Cor-

respondence Problem, Discrete Appl. Math. 130 (2003), 521 – 526. https://doi.org/10.1016/

S0166-218X(03)00330-5

[88] J. HAGE, T. HARJU, and E. WELZL, Euler graphs, triangle-free graphs and bipartite graphs in

switching classes, Fundamenta Informat. 58 (2003), 23 – 37.

[89] T. HARJU and D. NOWOTKA, About Duval extensions, Proc. 4th Internat. Conference on Com-

binatorics on Words (T. Harju, J. Karhum

aki, Eds.) (2003), 392 – 397.

[90] T. HARJU and D. NOWOTKA, Periodicity and unbordered segments of words, Column in For-

mal Language Theory (A. Salomaa, ed.) Bull. Eur. Assoc. Theor. Comput. Sci. 80 (2003),

162 – 167.

[91] T. HARJU, I. PETRE, and G. ROZENBERG, Gene assembly in ciliates: Molecular operations,

Column in Natural Computing (G. Rozenberg, ed.) Bull. Eur. Assoc. Theor. Comput. Sci. 81

(2003), 236 – 249. Reprinted in [112].

[92] T. HARJU, I. PETRE, and G. ROZENBERG, Tutorial on DNA computing and graph trans-

formation, Internat. Conference on Graph Transformations (ICGT’04, Rome; G. Engels et

Tero Harju (2020) 9

al., Eds.), Lecture Notes in Comput. Sci. 3256 (2004), 434 – 436. https://doi.org/10.1007/

978-3-540-30203-2 31

[93] T. HARJU, I. PETRE, and G. ROZENBERG, Gene assembly in ciliates, in Roadmap Report of

MolCoNet - A Thematic Network on Molecular Computing (European Union, IST-00-5-2B)

(2004), pp. 105 – 132.

[94] T. HARJU, I. PETRE, and G. ROZENBERG, Gene assembly in ciliates: Formal frameworks,

Column in Natural Computing (G. Rozenberg, ed.) Bull. Eur. Assoc. Theor. Comput. Sci. 82

(2004), 227 – 241. Reprinted in [113].

[95] A. EHRENFEUCHT, T. HARJU, I. PETRE, D.M. PRESCOTT, and G. ROZENBERG,

Computation in Living Cell. Gene Assembly in Ciliates, Springer-Verlag, 2004, xviii + 201

pages.

[96] T. HARJU and J. KARHUM

AKI (eds.), Proceedings of the 4th International Conference on

Combinatorics on Words (WORDS’03), TUCS, Painosalama, Turku 2003, vi + 420 pages.

[97] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Transitivity of local complementation

and switching on graphs, Discrete Math. 278 (2004), 45 – 60. https://doi.org/10.1016/j.disc.

2003.04.001

[98] A. EHRENFEUCHT, J. HAGE, T. HARJU, and G. ROZENBERG, Embedding in switching

classes with skew gains, Internat. Conference on Graph Transformations (ICGT’04, Rome;

G. Engels et al., eds.), Lecture Notes in Comput. Sci. 3256 (2004), 257 – 270. https://doi.org/

10.1007/978-3-540-30203-2 19

[99] T. HARJU and D. NOWOTKA, Periodicity and unbordered words, 21st Annual Symp. The-

oret. Aspects of Computer Science (STACS 2004, Montpellier, France; V. Diekert and

M. Habib, eds.), Lecture Notes in Comput. Sci. 2996 (2004), 294 – 304. https://doi.org/10.

1007/978-3-540-24749-4 26

[100] T. HARJU and D. NOWOTKA, Minimal Duval extensions, Internat. J. Foundations of Comput.

Sci. 15 (2004), 349 – 354. https://doi.org/10.1142/S0129054104002467

[101] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Zebra factorisations in free semigroups,

Semigroup Forum 68 (2004), 365 – 372. https://doi.org/10.1007/s00233-003-0030-z

[102] J. HAGE and T. HARJU, A characterization of acyclic switching classes using forbid-

den subgraphs, SIAM J. Discrete Math. 18 (2004), 159 – 176. https://doi.org/10.1137/

S0895480100381890

[103] T. HARJU and D. NOWOTKA, Border correlation of binary words, J. Combin. Theory, Ser. A

108 (2004), 331 – 341. https://doi.org/10.1016/j.jcta.2004.07.009

[104] V. HALAVA, T. HARJU, H.J. HOOGEBOOM, and M. LATTEUX, Valence languages generated

by equality sets, J. Autom. Lang. Comb. 9 (2004), 399 – 406.

Tero Harju (2020) 10

[105] V. HALAVA and T. HARJU, Undecidability in matrices over Laurent polynomials, Adv. Applied

Math. 33 (2004), 747 – 752. https://doi.org/10.1016/j.aam.2004.04.002

[106] T. HARJU and J. KARHUM

AKI, Many aspects of the defect effect, Theoret. Comput. Sci. 324

(2004), 35 – 54. https://doi.org/10.1016/j.tcs.2004.03.051

[107] T. HARJU and D. NOWOTKA, The equation x

= y

in a free semigroup, Semigroup Forum

68 (2004), 488 – 490. https://doi.org/10.1007/s00233-003-0028-6

[108] T. HARJU, I. PETRE, and G. ROZENBERG, Formal properties of gene assembly: equivalence

problem for overlap graphs, in Aspects of Molecular Computing - Essays dedicated to Tom

Head on the occasion of his 70th birthday (N.Jonoska et al., eds.), Lecture Notes in Comput.

Sci. 2950 Festschrift (2004), 202 – 212. https://doi.org/10.1007/978-3-540-24635-0

[109] T. HARJU, Combinatorics on words, in Formal Languages and Applications (C. Mart

ın-Vide

et al., eds.), Series: Studies in Fuzziness and Soft Computing, Vol. 148, Springer-Verlag, 2004,

381 – 392. https://doi.org/10.1007/978-3-540-39886-8 19

[110] A. EHRENFEUCHT, T. HARJU, I. PETRE, D.M. PRESCOTT, and G. ROZENBERG, Modelling

gene assembly in ciliates, in Modelling in Molecular Biology (G. Ciobanu and G. Rozenberg,

eds.), Natural Computing Series, Springer-Verlag, 2004, 105 – 204. https://doi.org/10.1007/

978-3-642-18734-6 5

[111] V. HALAVA and T. HARJU, Post Correspondence Problem – recent results, in Current Trends

in Theoretical Computer Science: The Challenge of the New Century (vol.1) (Gh. P

aun et al.,

eds.), World Scientiﬁc, 2004, 511 – 532. https://doi.org/10.1142/9789812562494 0062

[112] T. HARJU, I. PETRE, and G. ROZENBERG, Gene assembly in ciliates, Part I. Molecular oper-

ations, in Current Trends in Theoretical Computer Science: The Challenge of the New Cen-

tury (vol.2) (Gh. P

aun et al., eds.), World Scientiﬁc, 2004, 527 – 541. https://doi.org/10.1142/

9789812562494 0029

[113] T. HARJU, I. PETRE, and G. ROZENBERG, Gene assembly in ciliates, Part II. Operations for

gene assembly, in Current Trends in Theoretical Computer Science: The Challenge of the New

Century (vol.2) (Gh. P

aun et al., eds.), World Scientiﬁc, 2004, 543 – 557. https://doi.org/10.

1142/9789812562494 0030

[114] T. HARJU, I. PETRE, and G. ROZENBERG, Two models for gene assembly in ciliates, in Theory

is Forever (J. Karhum

aki et al., eds.), Lecture Notes in Comput. Sci. 3113 (2004), 89 – 101.

https://doi.org/10.1007/978-3-540-27812-2 9

[115] T. HARJU and D. NOWOTKA, On the equation x

= z

· · · z

in a free semigroup, Theo-

ret. Comput. Sci. 330 (2005), 117 – 121. https://doi.org/10.1016/j.tcs.2004.09.012

[116] T. HARJU, C. LI, I. PETRE, and G. ROZENBERG, Parallelism in gene assembly, Proc. 10th

Internat. Meeting on DNA Based Computers (DNA10, Milan; C. Ferretti et al, eds.), Lecture

Notes in Comput. Sci. 3384 (2005), 138 – 148. http://dx.doi.org/10.1007/s11047-005-4462-0

Tero Harju (2020) 11

[117] T. HARJU and M. MARGENSTERN, Splicing systems for universal Turing machines, Proc. 10th

Internat. Meeting on DNA Based Computers (DNA10, Milan; C. Ferretti et al., eds), Lecture

Notes in Comput. Sci. 3384 (2005), 151 – 160. https://doi.org/10.1007/11493785 13

[118] V. HALAVA, T. HARJU and M. LATTEUX, Equality sets of preﬁx morphisms and regular star

languages, Inform. Process. Lett. 94 (2005), 151 – 154. https://doi.org/10.1016/j.ipl.2005.01.014

[119] T. HARJU and D. NOWOTKA, Counting bordered and primitive words with a ﬁxed weight,

Theoret. Comput. Sci. 340 (2005) , 273 – 279. https://doi.org/10.1016/j.tcs.2005.03.040

[120] V. HALAVA, T. HARJU, H.J. HOOGEBOOM, and M. LATTEUX, Equality sets for recursively

enumerable languages, Theoret. Informatics Appl. 39 (2005), 661 – 675. https://doi.org/10.

1051/ita:2005035

[121] T. HARJU, A. LEPIST

O, and D. NOWOTKA, A characterization of periodicity of bi-inﬁnite

words, Theoret. Comput. Sci. 347 (2005), 419 – 422. https://doi.org/10.1016/j.tcs.2004.08.017

[122] T. HARJU, I. PETRE, V. ROGOJIN, and G. ROZENBERG, Simple operations for gene assembly,

DNA11 (London, Ontario) (2005); Lecture Notes in Comput. Sci. 3892 (2006), 96 – 111. http:

//dx.doi.org/10.1007/11753681 8

[123] T. HARJU, A combinatorial view on gene assembly, in Recent Results in Natural Computing,

(M. P

erez Jim

enez et al., eds.), Kronos Publishers, Sevilla, 2005, 79 – 104.

[124] T. HARJU, Combinatorial models of gene assembly, Proc. Computability in Europe, CiE 2005,

Amsterdam Lecture Notes in Comput. Sci. 3526 (2005), 188 – 195. https://doi.org/10.1007/

11494645 23

[125] V. HALAVA, T. HARJU and M. LATTEUX, Representation of regular languages by equality sets,

Bull. Eur. Assoc. Theor. Comput. Sci. 86 (2005), 224 – 228.

[126] T. HARJU, Characterization of regularity, Proc. FSMNLP 2005 (A. Yli-Jyr

a et al., Eds.), Lec-

ture Notes in Artiﬁcial Int. 4002 (2006), 1 – 8. https://doi.org/10.1007/11780885 1

[127] T. HARJU and D. NOWOTKA, Binary words with few squares, Bull. Eur. Assoc. Theor. Comput.

Sci. 89 (2006), 164 – 166.

[128] T. HARJU, J. KARHUM

AKI and A. RESTIVO (eds.), Combinatorics on Words, Special issue of

Theoret. Comput. Sci. 339 Issue 1, 2005, (pp. 1 – 165).

[129] V. HALAVA, T. HARJU, and M. HIRVENSALO, Positivity of second order linear recurrent se-

quences, Discrete Appl. Math. 154 (2006), 447 – 451. https://doi.org/10.1016/j.dam.2005.10.

009

[130] V. HALAVA, T. HARJU, and J. KARHUM

AKI, Undecidability in ω-regular languages, Funda-

menta Informat. 73 (2006), 119 – 125.

[131] T. HARJU and D. NOWOTKA, On unique factorizations of primitive words, Theoret. Comput.

Sci. 356 (2006), 186 – 189. http://dx.doi.org/10.1016/j.tcs.2006.01.031

Tero Harju (2020) 12

[132] T. HARJU, I. PETRE, and G. ROZENBERG, Modelling simple operations for gene assembly,

Natural Computing Series, Springer-Verlag, in “Nanotechnology: Science and Computation”

(Chen, J. et al., eds), Springer-Verlag 2006, 361 – 376. https://doi.org/10.1007/3-540-30296-4

[133] A. EHRENFEUCHT, J. HAGE, T. HARJU, and G. ROZENBERG, The embedding problem for

switching classes of graphs, Fundamenta Informat. 74 (2006), 115 – 134.

[134] T. HARJU, I. PETRE, C. LI, and G. ROZENBERG, Parallelism in gene assembly, Natural

Computing – An Internat. Journal (2006) 5 (2006), 203 – 223. https://doi.org/10.1007/

s11047-005-4462-0

[135] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Embedding linear orders in grids, Acta

Informat. 42 (2006), 419 – 428. https://doi.org/10.1007/s00236-005-0001-9

[136] T. HARJU and D. NOWOTKA, Periods in extensions of words, Acta Informat. 43 (2006), 165 –

171. http://dx.doi.org/10.1007/s00236-006-0014-z

[137] T. HARJU and J. KARHUM

AKI (eds.), Proceedings of the Workshop on Fibonacci Words 2006,

TUCS, Painosalama, Turku 2007.

[138] T. HARJU, J. KARHUM

AKI and A. LEPIST

O (eds.), Proceedings of Developments in Language

Theory. 11th International Conference, Lecture Notes in Comput. Sci. 4588, Springer–Verlag

2007.

[139] V. HALAVA and T. HARJU, Undecidability of inﬁnite Post Correspondence Problem for in-

stances of size 9, Theoret. Informatics Appl. 40 (2006), 551 – 557. http://dx.doi.org/10.1051/ita:

2006039

[140] J. HAGE and T. HARJU, On involutions arising from graphs, in “Algorithmic Bioprocesses,”

(Condon, A., Harel, D., Kok, J.N., Salomaa, A., Winfree, E., eds) Springer–Verlag, 2009, pp.

623 – 630. http://www.springer.com/computer/foundations/book/978-3-540-88868-0

[141] A. EHRENFEUCHT, T. HARJU, and G. ROZENBERG, Finite metrics in switching classes, Dis-

crete Appl. Math. 155 (2007), 68 – 73. http://dx.doi.org/10.1016/j.dam.2006.04.041

[142] V. HALAVA, T. HARJU, and J. KARHUM

AKI, Structure of inﬁnite solutions of marked and

binary Post Correspondence problems, Theory of Comput. Syst. 40 (2007) 43 – 54. http://dx.

doi.org/10.1007/s00224-005-1222-6

[143] T. HARJU, C. LI, I. PETRE, and G. ROZENBERG, Complexity measures for gene as-

sembly, Lecture Notes in Comput. Sci. 4366 (2007), 42 – 60. https://doi.org/10.1007/

978-3-540-71037-0 4

[144] V. HALAVA, T. HARJU, J. KARHUM

AKI and M. LATTEUX, Extensions of the decidability of

the marked PCP to instances with unique blocks, Theoret. Comput. Sci. 380 (2007), 355 – 362.

https://doi.org/10.1016/j.tcs.2007.03.024

Tero Harju (2020) 13

[145] T. HARJU and D. NOWOTKA, Periodicity and unbordered words: a proof of the extended Duval

conjecture, J. Assoc. Comput. Mach. 54 (2007). https://doi.org/10.1145/1255443.1255448

[146] V. HALAVA, T. HARJU, and M. HIRVENSALO, Undecidability bounds for integer matrices us-

ing Claus instances, Internat. J. Foundations of Comput. Sci. 18 (2007), 931 – 948. https:

//doi.org/10.1142/S0129054107005066

[147] V. HALAVA, T. HARJU, and T. K

ARKI, Relational codes of words, Theoret. Comput. Sci. 389

(2007), 237 – 249. https://doi.org/10.1016/j.tcs.2007.09.011

[148] V. HALAVA and T. HARJU, On Markov’s undecidability theorem for integer matrices, Semi-

group Forum 75 (2007), 173 – 180. https://doi.org/10.1007/s00233-007-0714-x

[149] J. HAGE and T. HARJU, Towards a characterization of bipartite switching classes by means of

forbidden subgraphs, Discussiones Mathematicae Graph Theory 27 (2007), 471 – 483. http:

//dx.doi.org/10.7151/dmgt.1374

[150] V. HALAVA, T. HARJU, and T. K

ARKI, Defect theorem with compatibility relations, Semigroup

Forum 76 (2008), 1 – 24. http://dx.doi.org/10.1007/s00233-007-9013-9

[151] J.-P. DUVAL, T. HARJU, and D. NOWOTKA, Unbordered Factors and Lyndon Words, Discrete

Math. 308 (2008), 2261 – 2264. http://dx.doi.org/10.1016/j.disc.2006.09.054

[152] T. HARJU, C. LI, and I. PETRE, Parallel complexity of signed graphs for gene assembly in

ciliates, Soft Computing 12 (2008), 731 – 737. http://dx.doi.org/10.1007/s00500-007-0233-4

[153] V. HALAVA, T. HARJU, and T. K

ARKI, Interaction properties of relational words, Discrete

Math. Theoret. Comput. Sci. 10 (2008), 87 – 112.

[154] V. HALAVA, T. HARJU, M. HIRVENSALO, and J. KARHUM

AKI, Post Correspondence Prob-

lem for short words, Inform. Process. Lett. 108 (2008), 115 – 118. http://dx.doi.org/10.1016/j.

ipl.2008.04.013

[155] V. HALAVA, T. HARJU, and T. K

ARKI, Square free partial words, Inform. Process. Lett. 108

(2008), 290 – 292. http://dx.doi.org/10.1016/j.ipl.2008.06.001

[156] T. HARJU, I. PETRE, V. ROGOJIN, and G. ROZENBERG, Patterns of simple gene assembly in

ciliates Discrete Appl. Math. 156 (2008), 2581 – 2597. http://dx.doi.org/10.1016/j.dam.2007.

09.026

[157] T. HARJU, C. LI, and I. PETRE, Graph theoretic approach to parallel gene assembly, Discrete

Appl. Math. 156 (2008), 3416 – 3429. http://dx.doi.org/10.1016/j.dam.2008.01.022

[158] T. HARJU and D. NOWOTKA, Bordered conjugates of words over large alphabets, Electronic

J. Combin 15(1) N41 (2008), 7 pages (electronic). https://doi.org/10.37236/916

[159] P. BELL, V. HALAVA, T. HARJU, J. KARHUM

AKI, and I. POTAPOV, Matrix equations and

Hilbert’s tenth problem, Internat. J. Algebra and Computation 18 (2008), 1 – 11. https:

//doi.org/10.1142/S0218196708004925

Tero Harju (2020) 14

[160] T. HARJU, Graph transformations related to gene assembly, Proc. of NCGT (Leicester 2008):

Workshop on Natural Computing and Graph Transformations (I. Petre and G.Rozenberg, Eds),

5 – 10. (2008).

[161] T. HARJU and J. KARHUM

AKI (eds.), Development of Language Theory, Special issue of In-

ternat. J. Foundations of Comput. Sci. 19 Issue 3 2008, (pp. 495 – 690).

[162] J. BERSTEL, T. HARJU and J. KARHUM

AKI (eds.), Fibonacci Words, Special issue of RAIRO

Inform. Th

eor. Appl. 42 Issue 4 2008, (pp. 657 – 762).

[163] T. HARJU, A. OKHOTIN, G. ROZENBERG, and A. SALOMAA (eds.), A Bird’s Eye View of The-

ory, Special issue of Theoret. Comput. Sci. 410 Issues 30–32, 2009, (pp. 2785 – 3034).

[164] T. HARJU, Post Correspondence Problem and small dimensional matrices, Lecture Notes in

Comput. Sci. 5583 (2009), 39 – 46. http://dx.doi.org/10.1007/978-3-642-02737-6 3

[165] V. HALAVA, T. HARJU, T. K

ARKI, and P. S

EBOLD, Overlap-freeness in inﬁnite partial words,

Theoret. Comput. Sci. 410 (2009), 943 – 948. http://dx.doi.org/10.1016/j.tcs.2008.12.041

[166] V. HALAVA, T. HARJU, and T. K

ARKI, The theorem of Fine and Wilf for relational periods,

RAIRO Inform. Th

eor. Appl. 40 (2009), 209 – 220. http://dx.doi.org/10.1051/ita:2008025

[167] T. HARJU and D. NOWOTKA, Cyclically repetition-free words on small alphabets, Inform. Pro-

cess. Lett. 110 (2010), 591 – 595. http://dx.doi.org/10.1016/j.ipl.2010.05.005

[168] V. HALAVA, T. HARJU, and T. K

ARKI, On the number of squares in partial words, Theoret.

Informatics Appl. 44 (2010), 125 – 138. http://dx.doi.org/10.1051/ita/2010008

[169] V. DIEKERT, T. HARJU and D. NOWOTKA, Weinbaum factorizations of primitive words (Rus-

sian), Izvestiya Vuzov. Matematika 2010 (1), 21-33. Translation: Russian Mathematics (Iz VUZ)

54 (1) (2010), 16-25. http://dx.doi.org/10.3103/S1066369X10010032

[170] V. HALAVA, T. HARJU, T. K

ARKI, and M. RIGO, On the periodicity of morphic words, Lecture

Notes in Comput. Sci. 6224 (DLT, London, Ontario) (2010), 209 – 217.

https://doi.org/10.1007/978-3-642-14455-4 20

[171] T. HARJU, Square-free walks on labelled graphs, http://arxiv.org/abs/1106.4106

[172] T. HARJU, Weinbaum factorizations (extended abstract), Oberwolfach Reports No. 37/2010

(1), 2212-2213. http://dx.doi.org/10.4171/OWR/2010/37

[173] T. HARJU, T. K

ARKI, and D. NOWOTKA The number of positions starting a square in binary

words, Electronic J. Combin 18(1) P6 (2011), 10 pages (electronic). https://doi.org/10.37236/

493

[174]

E. CHARLIER, M. DOMARATZKI, T. HARJU, and J. SHALLIT, Finite orbits of language op-

erations, Lecture Notes in Comput. Sci. 6638 (2011), 204 – 215. http://dx.doi.org/10.1007/

978-3-642-21254-3 15

Tero Harju (2020) 15

[175] T. HARJU and T. K

ARKI, On the number of frames in binary words, Theoret. Comput. Sci. 412

(2011), 5276 – 5284. http://dx.doi.org/10.1016/j.tcs.2011.05.032

[176] S. AZIMI, T. HARJU, M. LANGILLE, V. ROGOJIN, and I. PETRE, Directed overlap-inclusion

graphs as representations of ciliate genes, Fundamenta Informat. 110 (2011), 29 – 44. https:

//doi.org/10.3233/FI-2011-526

[177] V. HALAVA, T. HARJU, and T. K

ARKI, A new proof for the decidability of D0L ultimate peri-

odicity, EPTCS 63: Proc. WORDS’2011, 147 – 152. https://arxiv.org/abs/1108.3631

[178] T. HARJU, Square-free words obtained from preﬁxes by permutations, Theoret. Comput. Sci.

(2012) 429 (2012), 128 – 133. https://doi.org/10.1016/j.tcs.2011.12.031

[179] R. BRIJDER, T. HARJU, and H.J. HOOGEBOOM, Pivots, determinants, and perfect matchings

of graphs, Theoret. Comput. Sci. 454 (2012), 64 – 71. https://doi.org/10.1016/j.tcs.2012.02.031

[180] S. AZIMI, T. HARJU, M. LANGILLE, and I. PETRE, Simple gene assembly as a rewriting of

directed overlap-inclusion graphs, Theoret. Comput. Sci. 454 (2012), 30 – 37.

https://doi.org/10.1016/j.tcs.2012.04.018

[181] T. HARJU, Kuratowski closure operations on languages, in Proceedings of RuFiDim II, (Halava,

Karhum

aki, Matiyasevich, eds.) 2012, pp 5 – 10.

[182] T. HARJU and M. M

ULLER, Square-free words generated by applying permutations to a preﬁx,

in Proceedings of RuFiDim II, (Halava, Karhum

aki, Matiyasevich, eds.) 2012, pp 86 – 91.

[183] R. BRIJDER, M. DALEY, T. HARJU, N. JONOSKA, I. PETRE, and G. ROZENBERG, Com-

putational Gene Assembly in Ciliates, Chapter in the Handbook of Molecular Computing,

Vol. II, (Th.B

ack, J.Kok and G.Rozenberg, eds.), Springer-Verlag, 2012, pp 1233 – 1280.

http://www.springer.com/computer/foundations/book/978-3-540-92911-6

[184]

E. CHARLIER, M. DOMARATZKI, T. HARJU, and J. SHALLIT, Composition and Orbits of

Language Operations: Finiteness and Upper Bounds, Int. J. Comput. Math. 90 (2013), 1171 –

1196. http://dx.doi.org/10.1080/00207160.2012.681305

[185] T. HARJU, A note on square-free shufﬂes of words, Lecture Notes in Comput. Sci. 8079 (2013),

154 – 160. https://doi.org/10.1007/978-3-642-40579-2

[186] V. HALAVA and T. HARJU, New proof for the undecidability of the Circular PCP, Acta Infor-

matica 50 (2013), 331 – 341. https://doi.org/10.1007/s00236-013-0183-5

[187] V. HALAVA and T. HARJU, Word problem for deterministic and reversible semi-Thue systems.

Semigroup Forum 88 (2014), 468 – 478. http://dx.doi.org/10.1007/s00233-013-9550-3

[188] T. HARJU and T. K

ARKI, Minimal Similarity Relations for Square–Free Words, in Discrete

Mathematics and Computer Science. In Memoriam of Alexandru Mateescu (1952-2005), (Eds.

Gh. Paun, G. Rozenberg, A. Salomaa) Editura Academiei, Bucuresti (The Publishing House of

the Romanian Academy, Bucharest), 2014 pp. 193 – 200

Tero Harju (2020) 16

[189] T. HARJU, M. HUOVA, and L.Q. ZAMBONI, On generating binary words palindromically, J.

Combin. Theory Ser.A 129 (2015), 142 – 159. http://dx.doi.org/10.1016/j.jcta.2014.10.003

[190] T. HARJU and M. M

ULLER, A note on short palindromes in square-free words. Theoret. Com-

put. Sci. 562 (2015), 658 – 659. http://dx.doi.org/10.1016/j.tcs.2014.10.040

[191] V. HALAVA, T. HARJU, R. NISKANEN and I. POTAPOV, Weighted automata on inﬁnite words

in the context of Attacker-Defender games. Lecture Notes in Comput. Sci. (CiE 2015) 9136

(2015), 206 – 215. http://dx.doi.org/10.1007/978-3-319-20028-6 21

[192] V. HALAVA, T. HARJU, and M. HUOVA, On n-permutation Post Correspondence Problem

Theoret. Comput. Sci. 601 (2015), 15 – 20. http://dx.doi.org/10.1016/j.tcs.2015.07.021

[193]

E. CHARLIER, T. HARJU, S. PUZYNINA and L.Q. ZAMBONI, Abelian bordered factors and

periodicity, European J. Combin. 51 (2016), 407 – 418. http://dx.doi.org/10.1016/j.ejc.2015.07.

003

[194] T. HARJU and M. M

ULLER, Square-free shufﬂes of words, Theoret. Comput. Sci. 601 (2015),

29 – 38. http://dx.doi.org/10.1016/j.tcs.2015.07.024

[195] T. HARJU, J. VESTI, and L.Q. ZAMBONI, On a question of Hof, Knill and Simon on palin-

dromic substitutive systems, Monatshefte Math. 179 (2016), 379 – 388. http://dx.doi.org/10.

1007/s00605-015-0828-2

[196] V. HALAVA, T. HARJU and T. K

ARKI, Similarity relations on words, Chapter in Combina-

torics, Words and Symbolic Dynamics (V. Bert

e and M. Rigo, eds.), Cambridge University

Press 2016, pp. 183–220.

[197] V. HALAVA, T. HARJU, R. NISKANENand I. POTAPOV, Weighted automata on inﬁnite words

in the context of Attacker-Defender games, Information and Computation 255 (2017), 27 – 44.

http://dx.doi.org/10.1016/j.ic.2017.05.001

[198] V. HALAVA, T. HARJU, and E. SAHLA, A New Proof for the Undecidability of the Bi-Inﬁnite

Post’s Correspondence Problem, Fundamenta Informat. 154 (2017), 167 – 176. http://dx.doi.

org/10.3233/FI-2017-1558

[199] V. HALAVAand T. HARJU, Walks on Tilings of Polygons, Theoret. Comput. Sci. 701 (2017),

120 – 124. http://dx.doi.org/10.1016/j.tcs.2017.02.034

[200] V. HALAVA, T. HARJU, and E. SAHLA, On Fixed Points of Rational Transductions, Theoret.

Comput. Sci. 732 (2018), 85 – 88. https://doi.org/10.1016/j.tcs.2018.04.030

[201] T. HARJU, On Square-Free Arithmetic Progressions in Inﬁnite Words, Theoret. Comput. Sci.

770, 95 – 100. https://doi.org/10.1016/j.tcs.2018.09.032

[202] J. CURRIE, T. HARJU, P. OCHEM, and N. RAMPERSAD, Some further results on squarefree

arithmetic progressions in inﬁnite words, Theoret. Comput. Sci. 799, 140–148. https://doi.org/

10.1016/j.tcs.2019.10.006 https://arxiv.org/abs/1901.06351

Tero Harju (2020) 17

[203] T. HARJU and J. KARHUM

AKI, Transducers and Rational Transductions, Chapter 3 in Hand-

book of AutoMathA (J.-E. Pin, ed.), to appear.

[204] J. CASSAIGNE, V. HALAVA, T. HARJU, and F. NICOLAS, Tighter undecidability bounds for

matrix mortality, zero-in-the-corner problems, and more, submitted.

http://arxiv.org/abs/1404.0644

(G) Thesis

[205] T. HARJU, Simulation and Representation of Automata Using Auxiliary Tape Notation, Doc-

toral Dissertation, Department of Mathematics, University of Turku, 1979.

Special volume

VESA HALAVA, JUHANI KARHUM

AKI, DIRK NOWOTKA, GRZEGORZ ROZENBERG (eds), Words,

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

Fundamenta Informaticae 116, Numbers 1–4, 2012.

Lecture notes available online: Latest editions http://users.utu.fi/harju

T. HARJU, Graph Theory (2012)

T. HARJU, Ordered Sets (2012)

T. HARJU, Combinatorial Enumeration (2011)

T. HARJU, Semigroups (2017)

T. HARJU, Geometria (2015) in Finnish

T. HARJU, Logiikka (2009) in Finnish

T. HARJU, Automaatit, Formaaaliset kielet ja Laskettavuus (1998) in Finnish

T. HARJU, Combinatorial Structures in Graph Theory (2019)