Generating series are crucial in enumerative combinatorics, analytic combinatorics, and combinatorics on words. Though it might seem at first view that generating Dirichlet series are less used in these fields than or...
详细信息
Generating series are crucial in enumerative combinatorics, analytic combinatorics, and combinatorics on words. Though it might seem at first view that generating Dirichlet series are less used in these fields than ordinary and exponential generating series, there are many notable papers where they play a fundamental role, as can be seen in particular in the work of Flajolet and several of his co-authors. In this paper, we study Dirichlet series of integers with missing digits or blocks of digits in some integer base b;i.e., where the summation ranges over the integers whose expansions form some language strictly included in the set of all words over the alphabet {0,1, ... , b - 1} that do not begin with a 0. We show how to unify and extend results proved by Nathanson in 2021 and by K & ouml;hler and Spilker in 2009. En route, we encounter several sequences from Sloane's On-Line Encyclopedia of Integer Sequences, as well as some famous b-automatic sequences or b-regular sequences. We also consider a specific sequence that is not b-regular. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
We survey known results and open problems in abelian combinatorics on words. Abelian combinatorics on words is the extension to the commutative setting of the classical theory of combinatorics on words. The extension ...
详细信息
We survey known results and open problems in abelian combinatorics on words. Abelian combinatorics on words is the extension to the commutative setting of the classical theory of combinatorics on words. The extension is based on abelian equivalence, which is the equivalence relation defined in the set of words by having the same Parikh vector, that is, the same number of occurrences of each letter of the alphabet. In the past few years, there was a lot of research on abelian analogues of classical definitions and properties in combinatorics on words. This survey aims to gather these results.(c) 2022 Elsevier Inc. All rights reserved.
We survey several occurrences of combinatorics of words and morphisms in the pieces of Tom Johnson, showing in particular that some of the sequences of notes that he used intuitively can be interpreted or constructed ...
详细信息
We survey several occurrences of combinatorics of words and morphisms in the pieces of Tom Johnson, showing in particular that some of the sequences of notes that he used intuitively can be interpreted or constructed through combinatorial objects such as morphisms. Furthermore some of these sequences have an independent interest in number theory and theoretical computer science.
We describe an attempt to formalize some tasks in combinatorics on words using the assistance of Prover9, an automated theorem prover for first-order and equational logic.
ISBN:
(纸本)9783319587417;9783319587400
We describe an attempt to formalize some tasks in combinatorics on words using the assistance of Prover9, an automated theorem prover for first-order and equational logic.
The block reversal of a word w, denoted by BR(w), is a generalization of the concept of the reversal of a word, obtained by concatenating the blocks of the word in the reverse order. We characterize non-binary and bin...
详细信息
The block reversal of a word w, denoted by BR(w), is a generalization of the concept of the reversal of a word, obtained by concatenating the blocks of the word in the reverse order. We characterize non-binary and binary words whose block reversal contains only rich words. We prove that for a binary word w, richness of all elements of BR(w) depends on l(w), the length of the run sequence of w. We show that if all elements of BR(w) are rich, then 2 < l(w) < 8. We also provide the structure of such words. (c) 2023 Elsevier B.V. All rights reserved.
The class of (eventually) dendric words generalizes well-studied families such as the Sturmian words, the Arnoux-Rauzy words or the codings of interval exchanges. Dendricity is also a particular case of neutrality. We...
详细信息
The class of (eventually) dendric words generalizes well-studied families such as the Sturmian words, the Arnoux-Rauzy words or the codings of interval exchanges. Dendricity is also a particular case of neutrality. We show that, however, the notions of eventual dendricity and eventual neutrality coincide. This paper then focuses on two questions linking dendricity and morphisms. We first look at the evolution of the factor complexity when applying a non-erasing morphism to an eventually dendric word and show that it can only grow by an additive constant. We next generalize a result known for Sturmian words and consider the morphisms that preserve dendricity for all dendric words. We show that they correspond exactly to the morphisms generated by the Arnoux-Rauzy morphisms.
In 2013, while studying a relevant class of polyominoes that tile the plane by translation, i.e., double square polyominoes, Blondin Mass & eacute;et al. found that their boundary words, encoded by the Freeman cha...
详细信息
In 2013, while studying a relevant class of polyominoes that tile the plane by translation, i.e., double square polyominoes, Blondin Mass & eacute;et al. found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have specific interesting properties that involve notions of combinatorics on words such as palindromicity, periodicity and symmetry. Furthermore, they defined a notion of reducibility on double squares using homologous morphisms, so leading to a set of irreducible tile elements called prime double squares. The authors, by inspecting the boundary words of the smallest prime double squares, conjectured the strong property that no runs of two (or more) consecutive equal letters are present there. In this paper, we prove such a conjecture using combinatorics on words' tools, and setting the path to the definition of a fast generation algorithm and to the possibility of enumerating the elements of this class w.r.t. standard parameters, as perimeter and area. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).
We study the length of monochromatic arithmetic progressions in the Thue-Morse word and in a class of generalised Thue-Morse words. In particular, we give exact values or upper bounds for the lengths of monochromatic ...
详细信息
We study the length of monochromatic arithmetic progressions in the Thue-Morse word and in a class of generalised Thue-Morse words. In particular, we give exact values or upper bounds for the lengths of monochromatic arithmetic progressions of given fixed differences inside these words. Some arguments for these are inspired by van der Waerden's proof for the existence of arbitrary long monochromatic arithmetic progressions in any finite colouring of the (positive) integers. We also establish upper bounds for the length of monochromatic arithmetic progressions of certain differences in any fixed point of a primitive binary bijective substitution.(c) 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
The Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT [Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is based on the extended BWT of Mantaci et al. [TCS 2007...
详细信息
The Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT [Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is based on the extended BWT of Mantaci et al. [TCS 2007] and on the Lyndon factorization of the input string. In the original paper, the compression achieved with the BBWT was shown to be competitive with that of the BWT, and it has been gaining interest in recent years. In this work, we present the first study of the number rB of runs of the BBWT, which is a measure of its compression power. We exhibit an infinite family of strings on which rB of the string and of its reverse differ by a multiplicative factor of Theta(logn), where n is the length of the string. We also give several theoretical results on the BBWT, including a characterization of binary strings for which the BBWT has two runs. Finally, we present experimental results and statistics on r B ( s ) and r B ( s rev ), as well as on the number of Lyndon factors in the Lyndon factorization of s and s rev .
Although automatic sequences are algorithmically very simple, some of them have pseudorandom properties. In particular, some automatic sequences such as the Golay-Shapiro sequence are known to be 2-uncorrelated, meani...
详细信息
Although automatic sequences are algorithmically very simple, some of them have pseudorandom properties. In particular, some automatic sequences such as the Golay-Shapiro sequence are known to be 2-uncorrelated, meaning that they have the same correlations of order 2 as a uniform random sequence. However, the existence of l-uncorrelated automatic sequences (for l >= 3) was left as an open question in a recent paper of Marcovici, Stoll and Tahay. We exhibit binary block-additive sequences that are 3-uncorrelated and, with the help of analytical results supplemented by an exhaustive search, we present a complete picture of the correlation properties of binary block-additive sequences of rank r <= 5, and ternary sequences of rank r <= 3.
暂无评论