Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn balanced sequences and their critical exponent
51
0
0.0
(
0
)
Added by
Francesco Dolce
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study aperiodic balanced sequences over finite alphabets. A sequence v of this type is fully characterised by a Sturmian sequence u and two constant gap sequences y and y. We show that the language of v is eventually dendric and we focus on return words to its factors. We deduce a method computing critical exponent and asymptotic critical exponent of balanced sequences provided the associated Sturmian sequence u has a quadratic slope. The method is based on looking for the shortest return words to bispecial factors in v. We illustrate our method on several examples, in particular we confirm a conjecture of Rampersad, Shallit and Vandomme that two specific sequences have the least critical exponent among all balanced sequences over 9- resp. 10-letter alphabets.
rate research
Read More
We study ternary sequences associated with a multidimensional continued fraction algorithm introduced by the first author. The algorithm is defined by two matrices and we show that it is measurably isomorphic to the shift on the set ${1,2}^mathbb{N}$ of directive sequences. For a given set $mathcal{C}$ of two substitutions, we show that there exists a $mathcal{C}$-adic sequence for every vector of letter frequencies or, equivalently, for every directive sequence. We show that their factor complexity is at most $2n+1$ and is $2n+1$ if and only if the letter frequencies are rationally independent if and only if the $mathcal{C}$-adic representation is primitive. It turns out that in this case, the sequences are dendric. We also prove that $mu$-almost every $mathcal{C}$-adic sequence is balanced, where $mu$ is any shift-invariant ergodic Borel probability measure on ${1,2}^mathbb{N}$ giving a positive measure to the cylinder $[12121212]$. We also prove that the second Lyapunov exponent of the matrix cocycle associated with the measure $mu$ is negative.
A minimal absent word of a sequence x, is a sequence yt hat is not a factorof x, but all of its proper factors are factors of x as well. The set of minimal absent words uniquely defines the sequence itself. In recent times minimal absent words have been used in order to compare sequences. In fact, to do this, one can compare the sets of their minimal absent words. Chairungasee and Crochemorein [2] define a distance between pairs of sequences x and y, where the symmetric difference of the sets of minimal absent words of x and y is involved. Here, weconsider a different distance, introduced in [1], based on a specific subset of such symmetric difference that, in our opinion, better capture the different features ofthe considered sequences. We show the result of some experiments where the distance is tested on a dataset of genetic sequences by 11 living species, in order to compare the new distance with the ones existing in literature.
Given a graph $G = (V,E)$ with vertex weights $w(v)$ and a desired number of parts $k$, the goal in graph partitioning problems is to partition the vertex set V into parts $V_1,ldots,V_k$. Metrics for compactness, contiguity, and balance of the parts $V_i$ are frequent objectives, with much existing literature focusing on compactness and balance. Revisiting an old method known as striping, we give the first polynomial-time algorithms with guaranteed contiguity and provable bicriteria approximations for compactness and balance for planar grid graphs. We consider several types of graph partitioning, including when vertex weights vary smoothly or are stochastic, reflecting concerns in various real-world instances. We show significant improvements in experiments for balancing workloads for the fire department and reducing over-policing using 911 call data from South Fulton, GA.
The class of generating functions for completely monotone sequences (moments of finite positive measures on $[0,1]$) has an elegant characterization as the class of Pick functions analytic and positive on $(-infty,1)$. We establish this and another such characterization and develop a variety of consequences. In particular, we characterize generating functions for moments of convex and concave probability distribution functions on $[0,1]$. Also we provide a simple analytic proof that for any real $p$ and $r$ with $p>0$, the Fuss-Catalan or Raney numbers $frac{r}{pn+r}binom{pn+r}{n}$, $n=0,1,ldots$ are the moments of a probability distribution on some interval $[0,tau]$ {if and only if} $pge1$ and $pge rge 0$. The same statement holds for the binomial coefficients $binom{pn+r-1}n$, $n=0,1,ldots$.
We prove the existence of Veech groups having a critical exponent strictly greater than any elementary Fuchsian group (i.e. $>frac{1}{2}$) but strictly smaller than any lattice (i.e. $<1$). More precisely, every affine covering of a primitive L-shaped Veech surface $X$ ramified over the singularity and a non-periodic connection point $Pin X$ has such a Veech group. Hubert and Schmidt showed that these Veech groups are infinitely generated and of the first kind. We use a result of Roblin and Tapie which connects the critical exponent of the Veech group of the covering with the Cheeger constant of the Schreier graph of $mathrm{SL}(X)/mathrm{Stab}_{mathrm{SL}(X)}(P)$. The main task is to show that the Cheeger constant is strictly positive, i.e. the graph is non-amenable. In this context, we introduce a measure of the complexity of connection points that helps to simplify the graph to a forest for which non-amenability can be seen easily.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
