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.
This paper is contributed to the combinatorial properties of the MSS sequences, which are the periodic kneading words of quadratic maps defined on a interval. An explicit expression of adjacency relations on MSS seque...
详细信息
This paper is contributed to the combinatorial properties of the MSS sequences, which are the periodic kneading words of quadratic maps defined on a interval. An explicit expression of adjacency relations on MSS sequences of given lengths is established.
This paper is contributed to the combinatorial properties of the periodic kneading words of antisymmetric cubic maps defined on a interval. The least words of given lengths, the adjacency relations on the words of giv...
详细信息
This paper is contributed to the combinatorial properties of the periodic kneading words of antisymmetric cubic maps defined on a interval. The least words of given lengths, the adjacency relations on the words of given lengths and the parity-alternative property in some sets of such words are established.
The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classes of finite monoids. Their join is kn...
详细信息
The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classes of finite monoids. Their join is known to be decidable due to a result of Almeida and Azevedo. In this paper, we give a new proof for Almeida and Azevedo's effective characterization of the join of R-trivial and L-trivial monoids. This characterization is a single identity of omega-terms using three variables.
We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using finite automata and a software package for manipulating them. We illustrate our technique by applying it to (...
详细信息
We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using finite automata and a software package for manipulating them. We illustrate our technique by applying it to (a) solve an open problem of Currie and Saari on the lengths of unbordered factors in the Thue-Morse sequence;(b) verify an old result of Prodinger and Urbanek on the regular paperfolding sequence;(c) find an explicit expression for the recurrence function for the Rudin-Shapiro sequence;and (d) improve the avoidance bound in Leech's squarefree sequence. We also introduce a new measure of infinite words called condensation and compute it for some famous sequences. We follow up on the study of Currie and Saari of least periods of infinite words. We. show I hat the characteristic sequence of least periods of a k-automatic sequence is (effectively) k-automatic. We compute the least periods for several famous sequences. Many of our results were obtained by machine computations.
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.
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.
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 .
Derived sequence is an important theme in combinatorics on words. Let Sn,j be the infinite one-sided sequence over the alphabet {ad, 1 = 2 and j >= 1.
Derived sequence is an important theme in combinatorics on words. Let Sn,j be the infinite one-sided sequence over the alphabet {ad, 1 <= d <= n} generated by the substitution sigma n,j(ad)=a1jad+1 for 1 <= d= 2 and j >= 1.
暂无评论