SPSvetlana Puzynina

Svetlana Puzynina

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Svetlana Puzynina has a total of 22 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • On the Closed-Rich Constant of Infinite Words

    by Anuran Maity, Svetlana Puzynina

  • Open Access

    On the rigidity of Arnoux-Rauzy words

    by Valérie Berthé, Svetlana Puzynina

    An infinite word generated by a substitution is rigid if all the substitutions which fix this word are powers of a same substitution. Sturmian words as well as characteristic Arnoux-Rauzy words are known to be rigid. In the present paper, we prove that all Arnoux-Rauzy words are rigid. The proof relies on two main ingredients: firstly, the fact that the primitive substitutions that fix an Arnoux-Rauzy word share a common power, and secondly, the notion of normal form of an episturmian substitution (i.e., a substitution that fixes an Arnoux-Rauzy word). The main difficulty is then of a combinatorial nature and relies on the normalization process when taking powers of episturmian substitutions: the normal form of a square is not necessarily equal to the square of the normal forms.

  • Open Access

    Finite and infinite closed-rich words

    by Olga Parshina, Svetlana Puzynina

    A word is called closed if it has a prefix which is also its suffix and there is no internal occurrences of this prefix in the word. In this paper we study words that are rich in closed factors, i.e., which contain the maximal possible number of distinct closed factors. As the main result, we show that for finite words the asymptotics of the maximal number of distinct closed factors in a word of length $n$ is $\frac{n^2}{6}$. For infinite words, we show there exist words such that each their factor of length $n$ contains a quadratic number of distinct closed factors, with uniformly bounded constant; we call such words infinite closed-rich. We provide several necessary and some sufficient conditions for a word to be infinite closed rich. For example, we show that all linearly recurrent words are closed-rich. We provide a characterization of rich words among Sturmian words. Certain examples we provide involve non-constructive methods.

  • Open Access

    Abelian Nivat's conjecture for non-rectangular patterns

    by Nikolai Geravker, Svetlana Puzynina

    In this paper, we study the relation between periodicity of two-dimensional words and their abelian pattern complexity. A pattern $\cal{P}$ in $\mathbb{Z}^n$ is the set of all translations of some finite subset $F$ of $\mathbb{Z}^n$. An $F$-factor of an infinite word is a finite word restricted to $F$. Then the pattern complexity over a pattern $\mathcal{P}$ counts the number of distinct $F$-factors of an infinite word, for $P\in \mathcal{P}$. Two finite words are called abelian equivalent if for each letter of the alphabet, they contain the same numbers of occurrences of this letter. The abelian pattern complexity counts the number of $F$-factors up to abelian equivalence. As the main result of the paper, we characterize two-dimensional convex patterns with the following property: if abelian pattern complexity over a pattern $\cal{P}$ is equal to 1, then the word is fully periodic. Similar result holds for a function on $\mathbb{Z}^2$ instead of a word and for constant sums instead of abelian complexity equal to 1. In dimensional 1, we characterize patterns for which there exist non-constant functions with constant sums.

  • Open Access

    Abelian Closures of Infinite Binary Words

    by Svetlana Puzynina, Markus A. Whiteland

    Two finite words $u$ and $v$ are called Abelian equivalent if each letter occurs equally many times in both $u$ and $v$. The abelian closure $\mathcal{A}(\mathbf{x})$ of (the shift orbit closure of) an infinite word $\mathbf{x}$ is the set of infinite words $\mathbf{y}$ such that, for each factor $u$ of $\mathbf{y}$, there exists a factor $v$ of $\mathbf{x}$ which is abelian equivalent to $u$. The notion of an abelian closure gives a characterization of Sturmian words: among binary uniformly recurrent words, Sturmian words are exactly those words for which $\mathcal{A}(\mathbf{x})$ equals the shift orbit closure $\Omega(\mathbf{x})$. In this paper we show that, contrary to larger alphabets, the abelian closure of a uniformly recurrent aperiodic binary word which is not Sturmian contains infinitely many minimal subshifts.

  • Recurrence along directions in multidimensional words

    by Émilie Charlier, Svetlana Puzynina, Élise Vandomme

  • On abelian saturated infinite words

    by Sergey Avgustinovich, Julien Cassaigne, Juhani Karhumäki, Svetlana Puzynina, Aleksi Saarela


  • Open Access

    A characterization of words of linear complexity

    by Julien Cassaigne, Anna E. Frid, Svetlana Puzynina, Luca Q. Zamboni

    Given an infinite word $x=x_0x_1x_2\cdots \in \mathbb {A}^\mathbb {N}$ over some finite alphabet $\mathbb {A},$ the factor complexity $p_x(n)$ counts the number of distinct factors of $x$ of each given length $n,$ i.e., the number of distinct blocks $x_ix_{i+1}\cdots x_{i+n-1}\in \mathbb {A}^n$ occurring in $x.$ The factor complexity provides a useful measure of the extent of randomness of $x$: periodic words have bounded factor complexity while digit expansions of normal numbers have maximal complexity. In this paper we obtain a new characterization of infinite words $x$ of sublinear complexity, namely we show that $p_x(n)=O(n)$ if and only if there exists a set $S\subseteq \mathbb {A}^*$ of bounded complexity (meaning $\limsup p_S(n)<+\infty )$ such that each factor $w$ of $x$ is a concatenation of two elements of $S,$ i.e., $w=uv$ with $u,v \in S.$ In the process we introduce the notions of marker words and marker sets which are both new and may be of independent interest. Marker sets defined by right special factors constitute the key tool needed to split each factor of an infinite word of linear complexity into two pieces.