Publications 2000 - 2005
by Tero HarjuCombinatorics on words, automata
graph theory, combinatorics of DNAUpdated June 2008
- Most of the papers can be downloaded in postscript or pdf.
These are preprints (many from the TUCS technical report series).
Recent publications - 2005 - 2004 - 2003 - 2002 - 2001 - 2000 - From 1991 - 1999
My Homepage* 2005 *
Top of Page
- 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
- 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
- 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.
- 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
- 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
- Vesa Halava, Tero Harju, and Michel Latteux:
Representation of regular languages by equality sets
Bulletin of the EATCS 86 (2005), 225-228.
- 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
- 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
- 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
- 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
- Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux:
Valence languages generated by equality sets
J. Automata Lang. Combin. 9 (2004), 399-406.- 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
- 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
- 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- 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
- Tero Harju:
Combinatorics on words pdf file:
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.
- 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.
- Tero Harju and Dirk Nowotka:
Minimal Duval extensions
Internat. J. Foundations of Comput. Sci. 15 (2004), 349 - 354.
doi: 10.1142/S0129054104002467
- Tero Harju and Dirk Nowotka:
The equation aM = bN cP in a free semigroup (pdf file)
Semigroup Forum 68 (2004), 488 - 490.
doi:10.1007/s00233-003-0028-6
- 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
- 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.
- 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.
- 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
- 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
- Jurriaan Hage and Tero Harju:
A characterization of acyclic switching classes using forbidden subgraphs
SIAM J. Discrete Math. 18(1) (2004), 159 - 176.
doi: 10.1137/S0895480100381890
- Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, and Grzegorz Rozenberg:
Embedding in switching classes with skew gains
Proc. Internat. Conference on Graph Transformations (ICGT'04, Rome)
Lecture Notes in Comput. Sci. 3256 (2004), 257 - 270.
doi:10.1007/b100934
- 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.
- 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
- 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.) -->
- 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
- Tero Harju and Dirk Nowotka:
Periodicity and unbordered segments of words (pdf file)
Bulletin of the EATCS 80 (2003), 162 - 167.
- 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.
- Tero Harju and Grzegorz Rozenberg:
Computational processes in living cells: gene assembly in ciliates pdf file:
Lecture Notes in Comput. Sci. 2450 (2003), 1 - 20.
- 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
- 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
- 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
- Jurriaan Hage, Tero Harju and Emo Welzl:
Euler graphs, triangle-free and bipartite graphs in switching classes
Fundamenta Informaticae 58 (2003), 23 - 37.
Earlier version ICGT'02, October 2002. Lecture Notes in Comput. Sci. 2505 (2002), 148 - 160.
- 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).
- 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.
- 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
- Andrzej Ehrenfeucht, Tero Harju and Grzegorz Rozenberg:
Gene assembly in ciliates through circular graph decomposition
Theoret. Comput. Sci. 281 (2002), 325 - 349.
doi:10.1016/S0304-3975(02)00019-1
- 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.
- 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.
- 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.
- 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.
- 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.
- Tero Harju and Dirk Nowotka:
On the density of critical factorizations
Theoretical Informatics and Applications 36 (2002), 315 - 327.
doi:10.1051/ita:2002016
- 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.
- Vesa Halava and Tero Harju:
Some new results on Post Correspondence Problem and its generalizations
Bulletin of the EATCS 73 (2001), 131 - 141.
- Vesa Halava and Tero Harju :
Mortality in matrix semigroups
Amer. Math. Monthly 108 (2001), 649 - 653.
- Vesa Halava, Tero Harju and Lucian Ilie:
Periods and binary words
J. Combinat. Theory Ser. A, 89 (2000), 298 - 303.
- Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju and Grzegorz Rozenberg :
Complexity issues in switching of graphs
TAGT'98 (Ehrig, Engels, Kreowski, Rozenberg, eds)
Lecture Notes in Comput. Sci. 1764 (2000), 59 - 70.
- Jurriaan Hage and Tero Harju:
The size of switching classes with skew gains
Discrete Math. 215 (2000), 81 - 92.
- Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju and Grzegorz Rozenberg:
Pancyclicity in switching classes
Inform. Proc. Lett. 73 (2000), 153 - 156.
- 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/S0218196700000376See my
More recent publications
previous publications from 1991 - 1999
My Homepage