## Automata, Combinatorics on Words

and Graph Theory

by Tero Harju

Publications 1991 - 1999Updated Summer 2008

- Some of the papers can be downloaded in postscript or pdf.

These arepreprints.See also my

Recent publications

Publications 2000 - 2005

Back to my Homepage

The equivalence problem of multitape finite automata

Theoret. Comput. Sci.78 (1991), 347 - 355

(with J. Karhumäki )Decidability problems for unary output sequential transducers

Discrete Appl. Math.32 (1991), 131 - 139

(with H.C.M. Kleijn )Splicing semigroups of dominoes and DNA

Discrete Appl. Math.31 (1991), 261 - 277

(with K. Culik II )Compositional representation of rational functions

RAIRO Theoret. Inform.26 (1992), 243 - 255

(with H.C.M. Kleijn and M. Latteux )Deterministic sequential functions

Acta Informatica29 (1992), 545 - 554

(with H.C.M. Kleijn and M. Latteux )Permutable transformation semigroups

Semigroup Forum47 (1993), 123 - 125

(with A. Ehrenfeucht and G. Rozenberg )Morphisms and rational transducers

Bulletin of the EATCS51 (1993), 168 - 180

(with H.C.M. Kleijn )The intersection problem for alphabetic vector monoids

RAIRO Theoret. Inform.28 (1994), 295 - 301

(with N.W. Keesmaat and H.C.M. Kleijn )Representation of rational functions with

prefix and suffix codings

Theoret. Comput. Sci.134 (1994), 403 - 414

(with H.C.M. Kleijn, M. Latteux and A. Terlutte )Reductions for primitive 2-structures

Fundamenta Informaticae20 (1994), 133 - 144

(with G. Rozenberg )Incremental construction of 2-structures

Discrete Math.128 (1994), 113 -141

(with A. Ehrenfeucht and G. Rozenberg )Decomposition of infinite labeled 2-structures

Lecture Notes in CS812 (1994), 145 - 158

(with G. Rozenberg )Quotients and plane trees of group labeled 2-structures

GRAGRA'94 Proceedings(1994), 247 - 251

(with A. Ehrenfeucht and G. Rozenberg )Identities and transductions

Lecture Notes in CS128 (1994), 140 - 144

(with H.J. Hoogeboom and H.C.M. Kleijn )Compactness of systems of equations in semigroups

Lecture Notes in CS841 (1995), 443 - 452

(with J. Karhumäki and W. Plandowski )Remarks on generalized Post Correspondence problem

Lecture Notes in CS1046 (1996), 39 - 48

(with J. Karhumäki and D. Krob )Theory of 2-structures

Lecture Notes in CS841 (1995), 1 - 14

(with A. Ehrenfeucht and G. Rozenberg )Flatwords and Post Correspondence problem

Theoret. Comput. Sci.161 (1996), 93 - 108

(with M. Lipponen and Al. Mateescu )Characterization and complexity of uniformly nonprimitive labeled 2-structures

Theoret. Comput. Sci.154 (1996), 247 - 282

(with J. Engelfriet, G. Rozenberg and A. Proskurowski )Group based graph transformations and hierarchical representations of graphs

Lecture Notes in CS1073 (1996), 502 - 520

(with A. Ehrenfeucht and G. Rozenberg )Morphisms

in Handbook of Formal Languages, Vol 1. Word, Language, Grammar,

G. Rozenberg and A. Salomaa, eds., Springer-Verlag, 1997, pp. 439 - 510.

(with J. Karhumäki )A geometric problem of zig-zags

Inform. Proc. Letters,62 (1997), 1 - 4

(with V. Halava and L. Ilie )Compactness of systems of equations in semigroups

Internat. J of Algebra and Comput.7 (1997), 457 - 470

(with J. Karhumäki and W. Plandowski )2-structures: A framework for decomposition and transformation of graphs

Handbook of Graph Grammars and Computing by Graph Transformations,Vol. I. Foundations, World Scientific, 1997, pp. 411 - 488

(with A. Ehrenfeucht and G. Rozenberg )Invariants of inversive 2-structures on groups of labels

Mathematical Struct. Comput. Sci.7 (1997), 303 - 327

(with A. Ehrenfeucht and G. Rozenberg )A note on decidability questions on presentations of word semigroups

Theoret. Comput. Sci.183 (1997), 83 - 92

(with C. Choffrut and J. Karhumäki )Compactness of equations on completely regular semigroups

Lecture Notes in CS1261 (1997), 268 - 280

(with J. Karhumäki and M. Petrich )Languages obtained from infinite words

RAIRO Theoret. Inf.31 (1997), 445 -455

(with L. Ilie )On quasi orders of words and the confluence property

Theoret. Comput. Sci.200 (1998), 205 - 224

(with L. Ilie )Permutations, parenthesis words, and Schröder numbers

Discrete Math.,190 (1998), 259 - 264

(with A. Ehrenfeucht, P. ten Pas and G. Rozenberg )Acyclicity of switching classes

European J. of Combinatorics,19 (1998), 321 - 327.

(with J. Hage )Shuffle on trajectories: the Schützenberger product and related operations

Lecture Notes in Comput. Sci.1450 (1998), 503 -- 511.

(with Al. Mateescu and A. Salomaa )On the decidability of the freeness of matrix semigroups

Internat. J of Algebra and Comput.,9 (1999), 295 - 305.

(with J. Cassaigne and J. Karhumäki )Undecidability in integer weighted finite automata

Fundamenta Informaticae39 (1999), 189 - 200

(with V. Halava )Undecidability of the equivalence of finite substitutions

on regular languages

RAIRO Theoret. Inform.33 (1999), 117 - 124

(with V. Halava )Languages accepted by integer weighted finite automata

inJewels are Forever

(Karhumäki, Maurer, Paun, Rozenberg, eds), Springer Verlag, 1999, 123 - 134

(with V. Halava )The Theory of 2-Structures.

A framework for decomposition and transformation of graphs

World Scientific, 1999, xvi+290 pages

(with A. Ehrenfeucht and G. Rozenberg )