Author name cluster

Jarkko Peltomäki

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

I&C Journal 2022 Journal Article

Automatic winning shifts

Jarkko Peltomäki
Ville Salo

To each one-dimensional subshift X, we may associate a winning shift W ( X ) which arises from a combinatorial game played on the language of X. Previously it has been studied what properties of X does W ( X ) inherit. For example, X and W ( X ) have the same factor complexity and if X is a sofic subshift, then W ( X ) is also sofic. In this paper, we develop a notion of automaticity for W ( X ), that is, we propose what it means that a vector representation of W ( X ) is accepted by a finite automaton. Let S be an abstract numeration system such that addition with respect to S is a rational relation. Let X be a subshift generated by an S-automatic word. We prove that as long as there is a bound on the number of nonzero symbols in configurations of W ( X ) (which follows from X having sublinear factor complexity), then W ( X ) is accepted by a finite automaton, which can be effectively constructed from the description of X. We provide an explicit automaton when X is generated by certain automatic words such as the Thue-Morse word.

Details DOI

TCS Journal 2021 Journal Article

On prefix palindromic length of automatic words

Anna E. Frid
Enzo Laborde
Jarkko Peltomäki

The prefix palindromic length PPL u ( n ) of an infinite word u is the minimal number of concatenated palindromes needed to express the prefix of length n of u. Since 2013, it is still unknown if PPL u ( n ) is unbounded for every aperiodic infinite word u, even though this has been proven for almost all aperiodic words. At the same time, the only well-known nontrivial infinite word for which the function PPL u ( n ) has been precisely computed is the Thue-Morse word t. This word is 2-automatic and, predictably, its function PPL t ( n ) is 2-regular, but is this the case for all automatic words? In this paper, we prove that this function is k-regular for every k-automatic word containing only a finite number of palindromes. For two such words, namely the paperfolding word and the Rudin-Shapiro word, we derive a formula for this function. Our computational experiments suggest that generally this is not true: for the period-doubling word, the prefix palindromic length does not look 2-regular, and for the Fibonacci word, it does not look Fibonacci-regular. If proven, these results would give rare (if not first) examples of a natural function of an automatic word which is not regular.

Details DOI

MFCS Conference 2020 Conference Paper

All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words

Jarkko Peltomäki
Markus A. Whiteland

We consider repetitions in infinite words by making a novel inquiry to the maximum eventual growth rate of the exponents of abelian powers occurring in an infinite word. Given an increasing, unbounded function f: ℕ → ℝ, we construct an infinite binary word whose abelian exponents have limit superior growth rate f. As a consequence, we obtain that every nonnegative real number is the critical abelian exponent of some infinite binary word.

Details

TCS Journal 2020 Journal Article

More on the dynamics of the symbolic square root map

Jarkko Peltomäki
Markus A. Whiteland

In our earlier paper [Peltomäki and Whiteland (2017) [5]], we introduced a symbolic square root map. Every optimal squareful infinite word s contains exactly six minimal squares and can be written as a product of these squares: s = X 1 2 X 2 2 ⋯. The square root s of s is the infinite word X 1 X 2 ⋯ obtained by deleting half of each square. We proved that the square root map preserves the languages of Sturmian words (which are optimal squareful words). The dynamics of the square root map on a Sturmian subshift are well understood. In our earlier work, we introduced another type of subshift of optimal squareful words which together with the square root map form a dynamical system. In this paper, we study these dynamical systems in more detail and compare their properties to the Sturmian case. The main results are characterizations of periodic points and the limit set. The results show that while there is some similarity it is possible for the square root map to exhibit quite different behavior compared to the Sturmian case.

Details DOI

TCS Journal 2016 Journal Article

Abelian powers and repetitions in Sturmian words

Gabriele Fici
Alessio Langiu
Thierry Lecroq
Arnaud Lefebvre
Filippo Mignosi
Jarkko Peltomäki
Élise Prieur-Gaston

Richomme, Saari and Zamboni (2011) [39] proved that at every position of a Sturmian word starts an abelian power of exponent k for every k > 0. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period m starting at a given position in any Sturmian word of rotation angle α. By considering all possible abelian periods m, we recover the result of Richomme, Saari and Zamboni. As an analogue of the critical exponent, we introduce the abelian critical exponent A ( s α ) of a Sturmian word s α of angle α as the quantity A ( s α ) = lim sup k m / m = lim sup k m ′ / m, where k m (resp. k m ′ ) denotes the maximum exponent of an abelian power (resp. of an abelian repetition) of abelian period m (the superior limits coincide for Sturmian words). We show that A ( s α ) equals the Lagrange constant of the number α. This yields a formula for computing A ( s α ) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A ( s α ) ≥ 5 and that the equality holds for the Fibonacci word. We further prove that A ( s α ) is finite if and only if α has bounded partial quotients, that is, if and only if s α is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period F j, j > 1, has length F j ( F j + 1 + F j − 1 + 1 ) − 2 if j is even or F j ( F j + 1 + F j − 1 ) − 2 if j is odd, where F j is the jth Fibonacci number; ii) The minimum abelian period of any factor is a Fibonacci number. Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words: we prove that for j ≥ 3 the Fibonacci word f j, of length F j, has minimum abelian period equal to F ⌊ j / 2 ⌋ if j = 0, 1, 2 mod 4 or to F 1 + ⌊ j / 2 ⌋ if j = 3 mod 4.

Details DOI

TCS Journal 2013 Journal Article

Introducing privileged words: Privileged complexity of Sturmian words

Jarkko Peltomäki

In this paper we introduce a new class of so-called privileged words which have been previously considered only a little. We develop the basic properties of privileged words, which turn out to share similar properties with palindromes. Privileged words are studied in relation to previously studied classes of words, rich words, Sturmian words and episturmian words. A new characterization of Sturmian words is given in terms of privileged complexity. The privileged complexity of the Thue–Morse word is also briefly studied.

Details DOI