Combinatorics on words in symbolic dynamics: The quadratic map

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.     

复杂度为n+2的序列(英文)

本文研究了复杂度为n+2的序列.利用代换的理论以及词上组合的方法,刻画了这类序列,揭示了它们与Sturmian序列的密切联系.     

Some combinatorial properties of words in discrete dynamical systems from antisymmetric cubic maps

In this paper, we study the combinatorial properties ol words m chscrete dynamical systems from antisymmetric cubic maps. We also discuss the relationship of primitive kneading sequences of length n and period-doubling kneading sequences of length 2n, and then determine the number of all kneading sequences of length n.     

Symbolic analysis of finite words: the complexity function

We present several properties of the complexity function of finite words, the function counting the number of different factors in a word, for each length. To establish a first set of properties, we use the de Bruijn graphs and the suffix tree representations of a word. This allows us to show some inequalities that control the variation as well as the maximal value of the complexity function. Motivated by the applications, we discuss the change of the complexity function when sliding or increasing the size of a window laid down on a sequence to be analysed.     

Combinatorics on partial word correlations

Partial words are strings over a finite alphabet that may contain a number of “do not know” symbols. In this paper, we consider the period and weak period sets of partial words of length n over a finite alphabet, and study the combinatorics of specific representations of them, called correlations, which are binary and ternary vectors of length n indicating the periods and weak periods. We characterize precisely which vectors represent the period and weak period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. We show that the sets of all such vectors of a given length form distributive lattices under suitably defined partial orderings. We show that there is a well-defined minimal set of generators for any binary correlation of length n and demonstrate that these generating sets are the primitive subsets of {1,2,…,n−1}. We also investigate the number of partial word correlations of length n. Finally, we compute the population size, that is, the number of partial words sharing a given correlation, and obtain recurrences to compute it. Our results generalize those of Guibas, Odlyzko, Rivals and Rahmann.     

Testing primitivity on partial words

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program.     

Competitive symbolic integration in satellite dynamics

In this work, we shall compare a symbolic integration with a numerical integration of a test problem arising in satellite dynamics. An equatorial satellite with the J₂ effect in BF variables will be taken. As symbolic integrator, we shall take erewton©, a Maple V package implemented by the authors. Classical and contrasted numerical methods will be chosen to perform the numerical integration. We pointed out the advantages of symbolic integration as an efficient method for making very long time predictions on the orbit of the satellite.     

Avoiding abelian squares in partial words

Erd?s raised the question whether there exist infinite abelian square-free words over a given alphabet, that is, words in which no two adjacent subwords are permutations of each other. It can easily be checked that no such word exists over a three-letter alphabet. However, infinite abelian square-free words have been constructed over alphabets of sizes as small as four. In this paper, we investigate the problem of avoiding abelian squares in partial words, or sequences that may contain some holes. In particular, we give lower and upper bounds for the number of letters needed to construct infinite abelian square-free partial words with finitely or infinitely many holes. Several of our constructions are based on iterating morphisms. In the case of one hole, we prove that the minimal alphabet size is four, while in the case of more than one hole, we prove that it is five. We also investigate the number of partial words of length n with a fixed number of holes over a five-letter alphabet that avoid abelian squares and show that this number grows exponentially with n.     

Population dynamics with infinite Leslie matrices: finite time properties

Infinite Leslie matrices, introduced by Demetrius 40 years ago, are mathematical models of age-structured populations defined by a countable infinite number of age classes. This article is concerned with determining solutions of the discrete dynamical system in finite time. We address this problem by appealing to the concept of kneading matrices and kneading determinants. Our analysis is applicable not only to populations models, but also to models of self-reproducing machines and self-reproducing computer programs. The dynamics of these systems can also be described in terms of infinite Leslie matrices.     

Meromorphic symbolic structures for boundary value problems on manifolds with edges

We investigate the ideal of Green and Mellin operators with asymptotics for a manifold with edge‐corner singularities and boundary which belongs to the structure of parametrices of elliptic boundary value problems on a configuration with corners whose base manifolds have edges. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Substitution dynamical systems: Characterization of linear repetitivity and applications

We consider dynamical systems arising from substitutions over a finite alphabet. We prove that such a system is linearly repetitive if and only if it is minimal. Based on this characterization we extend various results from primitive substitutions to minimal substitutions. This includes applications to random Schrödinger operators and to number theory.     

Wavelet bases of Hermite cubic splines on the interval

In this paper a pair of wavelets are constructed on the basis of Hermite cubic splines. These wavelets are in C¹ and supported on [−1,1]. Moreover, one wavelet is symmetric, and the other is antisymmetric. These spline wavelets are then adapted to the interval [0,1]. The construction of boundary wavelets is remarkably simple. Furthermore, global stability of the wavelet basis is established. The wavelet basis is used to solve the Sturm–Liouville equation with the Dirichlet boundary condition. Numerical examples are provided. The computational results demonstrate the advantage of the wavelet basis. Dedicated to Dr. Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 42C40, 41A15, 65L60. Research was supported in part by NSERC Canada under Grants # OGP 121336.     

EQUIDISTRIBUTION OF CLOSED ORBITS OF BILLIARD FLOWS ON THE PLANE

The authors consider the billiard system with finitely many convex scatters with smooth boundary satisfying the visibility assumption on the plane and prove that the closed orbits for the billiard flow is uniformly distributed.     

A note about the truncation question in percolation of words

Consider an independent site percolation model on ℤ², with parameter p, equipped with all horizontal and vertical connections. In this note it is shown that given for any parameter p ∈ (0, 1), there exists an integer N such that any binary sequence (word) ξ ∈ {0, 1}^ℕ is seen, almost surely, even if all connections whose length is bigger than N are suppressed. *Partially supported by CNPq.     

On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}

In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research.     

Asymptotic analysis of quantum dynamics in crystals: the Bloch-Wigner transform, Bloch dynamics and Berry phase

We study the semi-classical limit of the Schro¨dinger equation in a crystal in the presence of an external potential and magnetic field. We first introduce the Bloch-Wigner transform and derive the asymptotic equations governing this transform in the semi-classical setting. For the second part, we focus on the appearance of the Berry curvature terms in the asymptotic equations. These terms play a crucial role in many important physical phenomena such as the quantum Hall effect. We give a simple derivation of these terms in different settings using asymptotic analysis.     

Specification on the interval

We study the consequences of discontinuities on the specification property for interval maps. After giving a necessary and sufficient condition for a piecewise monotonic, piecewise continuous map to have this property, we show that for a large and natural class of families of such maps (including the -transformations), the set of parameters for which the specification property holds, though dense, has zero Lebesgue measure. Thus, regarding the specification property, the general case is at the opposite of the continuous case solved by A.M. Blokh (Russian Math. Surveys 38 (1983), 133-134) (for which we give a proof).