Growth rates of power-free languages

We propose a new fast algorithm for calculating the growth rate of complexity for regular languages. Based on this algorithm, we develop an efficient universal method for estimating the upper bound of the growth rates for power-free languages. Through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds, and discover some general regularities.     

Lyapunov Exponents for the Random Product of Two Shears

We give lower and upper bounds on both the Lyapunov exponent and generalised Lyapunov exponents for the random product of positive and negative shear matrices. These types of random products arise in applications such as fluid stirring devices. The bounds, obtained by considering invariant cones in tangent space, give excellent accuracy compared to standard and general bounds, and are increasingly accurate with increasing shear. Bounds on generalised exponents are useful for testing numerical methods, since these exponents are difficult to compute in practice.

     

Maximum Rate of Growth of Enstrophy in Solutions of the Fractional Burgers Equation

This investigation is a part of a research program aiming to characterize the extreme behavior possible in hydrodynamic models by analyzing the maximum growth of certain fundamental quantities. We consider here the rate of growth of the classical and fractional enstrophy in the fractional Burgers equation in the subcritical and supercritical regimes. Since solutions to this equation exhibit, respectively, globally well-posed behavior and finite-time blowup in these two regimes, this makes it a useful model to study the maximum instantaneous growth of enstrophy possible in these two distinct situations. First, we obtain estimates on the rates of growth and then show that these estimates are sharp up to numerical prefactors. This is done by numerically solving suitably defined constrained maximization problems and then demonstrating that for different values of the fractional dissipation exponent the obtained maximizers saturate the upper bounds in the estimates as the enstrophy increases. We conclude that the power-law dependence of the enstrophy rate of growth on the fractional dissipation exponent has the same global form in the subcritical, critical and parts of the supercritical regime. This indicates that the maximum enstrophy rate of growth changes smoothly as global well-posedness is lost when the fractional dissipation exponent attains supercritical values. In addition, nontrivial behavior is revealed for the maximum rate of growth of the fractional enstrophy obtained for small values of the fractional dissipation exponents. We also characterize the structure of the maximizers in different cases.     

On possible growths of Toeplitz languages

We consider a new family of factorial languages whose subword complexity grows as Φ(n ^α ), where α is the only positive root of some transcendental equation. The asymptotic growth of the complexity function of these languages is studied by discrete and analytical methods, a corollary of the Wiener-Pitt theorem inclusive. The factorial languages considered are also languages of arithmetical factors of infinite words; so, we describe a new family of infinite words with an unusual growth of arithmetical complexity.     

循环矩阵本原指数的上界估计

本文给出了循环矩阵本原指数上界的新的估计及一种由级数较低的循环矩阵的本原指数估计级数较高的循环矩阵的本原指数的方法，解决了一类循环矩阵本原指数的计算问题．     

Determinants and Algebraic Identities Associated with the Root Systems of Classical Lie Algebras

Burnside asked questions about periodic groups in his influential paper of 1902. The study of groups with exponent six is a special case of the study of the Burnside questions on which there has been significant progress. It has contributed a number of worthwhile aspects to the theory of groups and in particular to computation related to groups. Finitely generated groups with exponent six are finite. We investigate the nature of relations required to provide proofs of finiteness for some groups with exponent six. We give upper and lower bounds for the number of sixth powers needed to define the largest 2-generator group with exponent six. We solve related questions about other groups with exponent six using substantial computations which we explain.     

Density and tails of unimodal convolution semigroups

We give sharp bounds for the isotropic unimodal probability convolution semigroups when their Lévy–Khintchine exponent has Matuszewska indices strictly between 0 and 2.     

The Convergence to Equilibrium of Neutral Genetic Models

This article is concerned with the long-time behavior of neutral genetic population models with fixed population size. We design an explicit, finite, exact, genealogical tree based representation of stationary populations that holds both for finite and infinite types (or alleles) models. We analyze the decays to the equilibrium of finite populations in terms of the convergence to stationarity of their first common ancestor. We estimate the Lyapunov exponent of the distribution flows with respect to the total variation norm. We give bounds on these exponents only depending on the stability with respect to mutation of a single individual; they are inversely proportional to the population size parameter.     

某一类控制系统中发生的指数偏差现象

我们考虑在某类控制系统中,以Lyapunov指数作为观测量,远离给定遍历测度的那些周期测度.对于这类周期测度的数量关于周期的指数增长率,我们将用测度熵在某个集合上的上界给出它的一个上限控制.     

Growth and uniqueness of rank

We prove that algebras of sub-exponential growth and, more generally, rings with a sub-exponential “growth structure” have the unique rank property. In the opposite direction the proof shows that if the rank is not unique one gets lower bounds on the exponent of growth. Fixing the growth exponent it shows that an isomorphism between free modules of greatly differing ranks can only be implemented by matrices with entries of logarithmically proportional high degrees.     

Coexistence in exotic scenarios of a modified Abrams–Strogatz model

We work on a model that has succeeded in describing real cases of coexistence of two languages within a closed community of speakers, taking into account bilingualism and incorporating a parameter to measure the distance between languages. The dynamics of this model depend on a characteristic exponent, which weighs the power of the size of a group of speakers to attract new members. So far, this model had been solved only when this characteristic exponent is greater than 1. In this article, we have managed to solve the nature of the stability of all the possible situations for this characteristic exponent, that is, when it is less or equal than 1 and covering also the situations produced when it is 0 or negative. We interpret these new situations and find that, even in such exotic scenarios, there are configurations of the resulting societies where all the languages coexist. © 2014 Wiley Periodicals, Inc. Complexity 21: 86–93, 2016     

A coupling approach to estimating the Lyapunov exponent of stochastic max-plus linear systems

This paper addresses the problem of approximately computing the Lyapunov exponent of stochastic max-plus linear systems. Our approach allows for an efficient simulation of bounds for the Lyapunov exponent. We provide sufficient conditions for the convergence of the bounds. In particular, a perfect sampling scheme for the Lyapunov exponent is established. We illustrate the effectiveness of our bounds with an application to (real-life) railway systems.     

On the word problem for syntactic monoids of piecewise testable languages

Piecewise testable languages are widely studied area in the theory of automata. We analyze the algebraic properties of these languages via their syntactic monoids. In this paper a normal form is presented for 2- and 3-piecewise testable languages and a log-asymptotic estimate is given for the number of words over these monoids.     

On fully indecomposable exponent for primitive boolean matrices with symmetric ones

If A is a primitive matrix, then there is a smallest power of A (its fully indecomposable exponent) which is fully indecomposable, and a smallest power of A (its strict fully indecomposable exponent) starting from which all powers are fully indecomposable. We obtain bounds on these two exponents for primitive Boolean matrices with symmetric one's.     

Quasiconformal groups and a theorem of Biship and Jones

We provide new bounds on the exponent of convergence of a planar discrete quasiconformal group in terms of the associated dilatation and the Hausdorff dimension of its conical limit set. In doing so, we use these bounds to realize a theorem of C. Bishop and P. Jones as an asymptotic limit in the dilatation.     

Counting closed geodesics in globally hyperbolic maximal compact AdS 3-manifolds

We propose a definition for the length of closed geodesics in a globally hyperbolic maximal compact (GHMC) Anti-De Sitter manifold. We then prove that the number of closed geodesics of length less than R grows exponentially fast with R and the exponential growth rate is related to the critical exponent associated to the two hyperbolic surfaces coming from Mess parametrization. We get an equivalent of three results for quasi-Fuchsian manifolds in the GHMC setting: Bowen’s rigidity theorem of critical exponent, Sanders’ isolation theorem and McMullen’s examples lightening the behaviour of this exponent when the surfaces range over Teichmüller space.     

Pseudo-moderate deviations in the euler method for real diffusion process

We consider the problem of the non-sequential detection of a change in the drift coefficient of a stochastic differential equation, when a misspecified model is used. We formulate the generalized likelihood ratio (GLR) test for this problem, and we study the behaviour of the associated error probabilities (false alarm and nodetection) in the small noise asymptotics. We obtain the following robustness result: even though a wrong model is used, the error probabilities go to zero with exponential rate, and the maximum likelihood estimator (MLE) of the change time is consistent, provided the change to be detected is larger (in some sense) than the misspecification error. We give also computable bounds for selecting the threshold of the test so as to achieve these exponential rates.     

A note on geometric upper bounds for the exponent of convergence of convex cocompact Kleinian groups

In this note we obtain by purely geometric means that for convex cocompact Kleinian groups the exponent of convergence is bounded from above by an expression which depends mainly on the diameter of the convex core of the associated infinite-volume hyperbolic manifold. This result is derived via refinements of Sullivan's shadow lemma and of estimates for the growth of the orbital counting function and Poincaré series. We finally obtain spectral and fractal implications, such as lower bounds for the bottom of the spectrum of the Laplacian on these manifolds, and upper bounds for the decay of the area of neighbourhoods of the associated limit sets.     

Computing the partial word avoidability indices of ternary patterns

We study pattern avoidance in the context of partial words. The problem of classifying the avoidable binary patterns has been solved, so we move on to ternary and more general patterns. Our results, which are based on morphisms (iterated or not), determine all the ternary patternsʼ avoidability indices or at least give bounds for them.     

On the spectrum of the Page and the Chen–LeBrun–Weber metrics

We give bounds on the first non-zero eigenvalue of the scalar Laplacian for both the Page and the Chen–LeBrun–Weber Einstein metrics. One notable feature is that these bounds are obtained without explicit knowledge of the metrics or numerical approximation to them. Our method also allows the estimation of the invariant part of the spectrum for both metrics. We go on to discuss an application of these bounds to the linear stability of the metrics. We also give numerical evidence to suggest that the bounds for both metrics are extremely close to the actual eigenvalue.