Svetlana Puzynina
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
Research Subjects
Svetlana Puzynina has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Anna E. Frid
Aix Marseille Univ CNRS Centrale Marseille I2M Marseille France
7 shared publications - Sergey V. Avgustinovich
Sobolev Institute of Mathematics, Novosibirsk, Russia
6 shared publications - Julien Cassaigne
UMR 7373 CNRS Aix Marseille Université I2M 13331 Marseille France
5 shared publications - Markus A. Whiteland
Department of Computer Science, Loughborough University, Loughborough, UK
5 shared publications - Juhani Karhumäki
University of Turku
4 shared publications - Luca Q. Zamboni
UMR 5208 Université de Lyon Université Lyon 1 CNRS Institut Camille Jordan 43 boulevard du 11 novembre 1918 F69622 Villeurbanne Cedex France
4 shared publications
Latest Publications
- 30 June 2025
- Published by Springer Nature
- p. 217-229
On the Closed-Rich Constant of Infinite Words
- Open Access
On the rigidity of Arnoux-Rauzy words
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 AccessOn the rigidity of Arnoux-Rauzy words
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
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 AccessFinite and infinite closed-rich words
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
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 AccessAbelian Nivat's conjecture for non-rectangular patterns
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
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.Open AccessAbelian Closures of Infinite Binary Words
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. - 1 October 2020
- Published by Elsevier in Discrete Mathematics
- Vol. 343 (10)
Recurrence along directions in multidimensional words
- 1 October 2020
- Published by Elsevier in Discrete Mathematics
- Vol. 343 (10)
Recurrence along directions in multidimensional words
- 1 November 2019
- Published by Elsevier in Theoretical Computer Science
- Vol. 792, 154-160
On abelian saturated infinite words
- 1 November 2019
- Published by Elsevier in Theoretical Computer Science
- Vol. 792, 154-160
On abelian saturated infinite words
- Open Access
- 3 April 2019
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 147 (7) , 3103-3115
A characterization of words of linear complexity
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.- 3 April 2019
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 147 (7) , 3103-3115
Open AccessA characterization of words of linear complexity
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.