It is well known that the set of powers of any given order, for example squares, in a regular language need not be regular. Nevertheless, finite automata can identify them via their roots. More precisely, we recall that, given a regular language L, the set of square roots of L is regular. The same holds true for the nth roots for any n and for the set of all nontrivial roots; we give a concrete construction for all of them. Using the above result, we obtain decision algorithms for many natural problems on powers. For example, it is decidable, given two regular languages, whether they contain the same number of squares at each length. Finally, we give an exponential lower bound on the size of automata identifying powers in regular languages. Moreover, we highlight interesting behavior differences between taking fractional powers of regular languages and taking prefixes of a fractional length. Indeed, fractional roots in a regular language can typically not be identified by finite automata.

Two words u and v are said to be k-abelian equivalent if, for each word x of length at most k, the number of occurrences of x as a factor of u is the same as for v. We study some combinatorial properties of k-abelian equivalence classes. Our starting point is a characterization of k-abelian equival ence by rewriting, so-called k-switching. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k-abelian equivalence classes is a regular language. From this we infer that the sequence of the numbers of equivalence classes is ℕ-rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size.

This special issue is devoted to various areas in Theoretical Computer Science. The issue took \ninspiration from the 13th Italian Conference on Theoretical Computer Science (ICTCS 2012), held at \nUniversity of Insubria in Varese, Italy, on September 19-21 2012. The special issue contains seven \npapers, that have been originated from the work in progress presented at the conference, and that have \nbeen accepted for publication after a rigorous review process and revisions. \nWe kindly thank all the authors of the published papers, as well as all the participants to ICTCS 2012, \nwho make it such an exciting event. \nWe are very grateful to the referees who devoted their precious time to produce thorough reviews. \nTheir valuable comments and suggestions improved a lot the submitted manuscripts. \nWe are especially thankful to Professor Damian Niwinski, Editor-in-Chief of Fundamenta Informaticae, \nfor accepting this special issue and for his help throughout the publication process. \nLastly, we wish to dedicate this special issue to the memory of Professor Alberto Bertoni, who was \none of the co-founders of the Italian chapter of the European Association for Theoretical Computer \nScience, and passed away on February 2014.

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

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.

We show by a simple reduction that the unique decipherability problem in the language monoid of regular languages over a non-unary alphabet is undecidable.

Classically, several properties and relations of words, such as “being a power of the same word” can be expressed by using word equations. This paper is devoted to a general study of the expressive power of word equations. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, “the primitiveness” and “the equal length” are such properties, as well as being “any word over a proper subalphabet”.

We show a simple O(n log n) time algorithm computing the order of repetition in a string. A parallel version of the algorithm works in O(log

We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However, as we show, the prefix rank forms an exception.

Weighted Finite Automata are automata with multiplicities used to compute real functions by reading infinite words. The aim of this paper is to study what kind of functions can be computed by level automata, a particular subclass of WFA. Several results concerning the continuity and the smoothness of these functions are shown. In particular, the only smooth functions that can be obtained are the polynomials. This enables to decide whether a function computed by a level automaton is smooth or not.

A new application of finite automata as computers of real functions is introduced. It is shown that even automata with a restricted structure compute all polynomials, many fractal-like and other functions. Among the results shown, the authors give necessary and sufficient conditions for continuity, show that continuity and equivalence are decidable properties, and show how to compute integrals of functions in the automata representation.

The equivalence problem for deterministic two-way transducers was a longstanding problem finally shown decidable by E. M. Gurari. We show a generalization of this result, namely that it is decidable whether two single-valued two-way transducers are equivalent on an NPDTOL language. We obtain this result by showing that it is even decidable whether a two-way transducer is single-valued on an NPDTOL language. Our solution is based on the compactness property of the systems of equations over a finitely generated free monoid shown recently by J. Lawrence and M. Albert and also V. S. Guba. This was a longstanding open problem known as the Ehrenfeucht Conjecture. Our approach also shows that for one-way transducers their single-valuedness on a given HDTOL language can be tested, and thus the equivalence of two single-valued one-way transducers on an HDTOL language is decidable, too. Our results imply the decidability of the HDOL and HDTOL sequence equivalence problems, also longstanding open problems solved recently by K. Ruohonen and the authors, respectively.