We study decision problems of the form: given a regular or linear context-free language L, is there a word of a given fixed form in L, where given fixed forms are based on word operations copy, marked copy, shuffle and their combinations.

We present a construction to simulate Turing machines with 3×3 matrices over rationals. The correctness of simulation is guaranteed by testing that the matrices have integral elements during the simulation. This construction implies an undecidability result for a special identity problem for semigroups of 3×3-matrices.

Denote by ш the operation of interleaving, or shuffling, of words. We prove that, given a regular language R and a letter-to-letter morphism φ, it is undecidable whether or not there exists a word ω such that ω ш φ(ω) ∩ R ≠ ø.

We give a new simplified proof for undecidability of the Bi-Infinite Post Correspondence Problem (ℤPCP). We reduce the special case of the word problem of semi-Thue systems to ℤPCP.

The termination problem for semi-Thue systems asks whether all derivations for a given word in a given semi-Thue system are finite, i.e., all derivations terminate after finite number of steps. This problem is known to be undecidable, there is a standard reduction of the halting problem of the Turi ng machines into termination problem; moreover, one can fix a semi-Thue system and still have the undecidability. In 1996 Sénizergues and the second author gave a construction for a 3-rule semi-Thue system with undecidable termination problem. However, in their construction the words of one of the rules are very long. Using some ideas of Tseijtin we give a construction for a semi-Thue system with low number of short rules having undecidable termination problem. Namely, we construct a semi-Thue system with 24 rules over 8 letter alphabet with rule words of length at most 5, and the termination problem for this semi-Thue system is undecidable. Moreover, this system is universal, that is, it can simulate any semi-Thue system.

Institute of St. Petersburg.The second event took place in Turku on September 25-28

We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert's tenth problem.

This special issue celebrates the 60th birthday of Professor Tero Harju (the actual birthday date is June 28, 2012).It consists of 20 original contributions written by his friends, colleagues and former students.The topics of this issue cover a broad spectrum of theoretical computer science and discrete mathematics, from automata theory via combinatorics on words to biomodelling -this coverage ref ects an impressive range of scientif c interest and research contributions by Tero.He made impressive scientif c contributions to many research areas including formal languages and automata theory, combinatorics on words, semigroup theory, computability theory, DNA computing, and biomodelling.Many of his results belong to highlights of those areas.His contributions to science are twofold: he solved many very challenging technical problems and he was also instrumental in shaping new research directions.One can mention here his solutions of famous open problems such as the equivalence problem of multitape f nite automata and Duval's conjecture on periodicity of words as examples of the former, and his work on regularity of splicing systems and the work on a formal framework for gene assembly in cilliates as examples of the latter.Tero is a Full Professor in the department of mathematics of University of Turku, Finland, and a member of Finnish Academy of Sciences.Although he stayed at a number of scientif c institutions abroad, his real nest is the combination of the department in Turku and his home in Lieto, not far from Turku.Still, thanks to the Internet and many travels to conferences where he presents his results, he has an impressive number of co-authors, mostly in Europe and North America.All four of us have extensive experience of working with Tero.The working sessions are long and intense, but they are often punctuated by bursts of laughing when Tero utters one of his one-liners: he has a wonderful sense of dry intellectual humor.Another characteristic feature of Tero is his remarkable modesty -he just lets his results speak for him.No wonder that Tero is popular in the scientif c community -the response to our call for papers to this special issue was enthusiastic indeed.

It is shown that the universe problem L(Aγ ) = A* is undecidable for 4-state finite automata A with integer weight function γ on its transitions. This holds even in the case, where A is acyclic and the weighting γ satisfies the unimodality condition.