On two-sided infinite fixed points of morphisms

Let Σ be a finite alphabet, and let h:Σ^* → Σ^* be a morphism. Finite and infinite fixed points of morphisms—i.e., those words w such that h(w)=w—play an important role in formal language theory. Head characterized the finite fixed points of h, and later, Head and Lando characterized the one-sided infinite fixed points of h. Our paper has two main results. First, we complete the characterization of fixed points of morphisms by describing all two-sided infinite fixed points of h, for both the “pointed” and “unpointed” cases. Second, we completely characterize the solutions to the equation h(xy)=yx in finite words.     

Reversals and palindromes in continued fractions

Several results on continued fractions expansions are on indirect consequences of the mirror formula. We survey occurrences of this formula for Sturmian real numbers, for (simultaneous) Diophantine approximation and for formal power series.     

Special factors and the combinatorics of suffix and factor automata

The suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages L_SA and L_FA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.     

De Bruijn sequences and De Bruijn graphs for a general language

A de Bruijn sequence over a finite alphabet of span n is a cyclic string such that all words of length n appear exactly once as factors of this sequence. We extend this definition to a subset of words of length n, characterizing for which subsets exists a de Bruijn sequence. We also study some symbolic dynamical properties of these subsets extending the definition to a language defined by forbidden factors. For these kinds of languages we present an algorithm to produce a de Bruijn sequence. In this work we use graph-theoretic and combinatorial concepts to prove these results.     

New method for quantification of clastic sedimentary sequences in time series analysis

Parameters related to the lithology of a clastic sequence may be used for its quantification. Settling velocity of constituent grains of a bed, which is one such parameter, has been taken as a basis for the numerical characterization of clastic rocks and the construction of a stratigraphic time-series representing the sequence. In order to account for varying bed thickness, one may divide an entire section into subsections of equal thickness, varying from 0.1 to 1.0 m. depending on the problem and the nature of data. For each subsection the proportions of thickness of different constituent clastic beds then are multiplied by modified settling velocity values corresponding to their respective grain size characteristics. The resulting numbers are added for each subsection to form the depth series to be analyzed. The proposed method is explained with the help of a case study based on three sections of clastic sequences obtained from the Gondwana coal fields in India. The depth series constructed from the sections have been analyzed by time-series methods. Results of the analysis have been used to demonstrate the applicability of the method in stratigraphic correlation.     

On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters

We give lower bounds on the growth rate of Dejean words, i.e. minimally repetitive words, over a k-letter alphabet, for 5≤k≤10. Put together with the known upper bounds, we estimate these growth rates with the precision of 0.005. As a consequence, we establish the exponential growth of the number of Dejean words over a k-letter alphabet, for 5≤k≤10.     

Balancing and clustering of words in the Burrows-Wheeler transform

Compression algorithms based on Burrows-Wheeler transform (BWT) take advantage of the fact that the word output of BWT shows a local similarity and then turns out to be highly compressible. The aim of the present paper is to study such “clustering effect” by using notions and methods from Combinatorics on Words.The notion of balance of a word plays a central role in our investigation. Empirical observations suggest that balance is actually the combinatorial property of input word that ensure optimal BWT compression. Moreover, it is reasonable to assume that the more balanced the input word is, the more local similarity we have after BWT (and therefore the better the compression is). This hypothesis is here corroborated by experiments on “real” text, by using local entropy as a measure of the degree of balance of a word.In the setting of Combinatorics on Words, a sound confirmation of previous hypothesis is given by a result of Mantaci et al. (2003) [27], which states that, in the case of a binary alphabet, there is an equivalence between circularly balanced words, words having a clusterized BWT, and the conjugates of standard words. In the case of alphabets of size greater than two, there is no more equivalence. The last section of the present paper is devoted to investigate the relationships between these notions, and other related ones (as, for instance, palindromic richness) in the case of a general alphabet.     

Relation between powers of factors and the recurrence function characterizing Sturmian words

In this paper we use the relation of the index of an infinite aperiodic word and its recurrence function to give another characterization of Sturmian words. As a by-product, we give a new proof of the theorem describing the index of a Sturmian word in terms of the continued fraction expansion of its slope. This theorem was independently proved in [A. Carpi, A. de Luca, Special factors, periodicity, and an application to Sturmian words, Acta Inform. 36 (2000) 983–1006] and [D. Damanik, D. Lenz, The index of Sturmian sequences, European J. Combin. 23 (2002) 23–29].     

线性有限自动机的UIO序列及其生成算法

对线性有限自动机的UIO序列进行了讨论,得到了线性有限自动机的任意一状态有某一长度的UIO序列的充要条件,得到了线性有限自动机的(所有)状态有UIO序列的的充要条件,还给出了有UIO序列的线性有限自动机的状态的最短UIO序列长度的上界,最后给出了判断线性有限自动机的所有状态有无UIO序列以及有求其UIO序列的两个算法.     

Subanalytic solutions of linear difference equations and multidimensional hypergeometric sequences

We consider linear difference equations with polynomial coefficients over C and their solutions in the form of sequences indexed by the integers (sequential solutions). We investigate the C-linear space of subanalytic solutions, i.e., those sequential solutions that are the restrictions to Z of some analytic solutions of the original equation. It is shown that this space coincides with the space of the restrictions to Z of entire solutions and that the dimension of this space is equal to the order of the original equation.We also consider d-dimensional (d≥1) hypergeometric sequences, i.e., sequential and subanalytic solutions of consistent systems of first-order difference equations for a single unknown function. We show that the dimension of the space of subanalytic solutions is always at most 1, and that this dimension may be equal to 0 for some systems (although the dimension of the space of all sequential solutions is always positive).Subanalytic solutions have applications in computer algebra. We show that some implementations of certain well-known summation algorithms in existing computer algebra systems work correctly when the input sequence is a subanalytic solution of an equation or a system, but can give incorrect results for some sequential solutions.     

Unsupervised extraction of patterns and trends within highway systems condition attributes data

Highway agencies combine expert opinions and basic regression modeling techniques to process vast amounts of time series condition attributes data to define highway network health. The health rating exhibit high variability and lack adequate detail for executive-level maintenance planning and resource allocation. This paper presents a new methodology for data abstraction, analysis, and clustering for pattern recognition of highway network health. The methodology describes mathematical and statistical data abstraction algorithms for data preprocessing (smoothening (unweighted moving average), scaling (normalization), and weights derivation (entropy) to compute a composite health index (CHI)), and salient features extraction. Data analysis involved cluster analysis to identify patterns in asset current health and future outlook. The outcome is a characterization of highway network health for executive-level decision making. The algorithms included in this methodology have been successfully applied in the fields of biology, finance, econometrics, bioinformatics, marketing, and social science for pattern recognition. The accuracy of the new methodology is illustrated with an experiment using 463 in-service pavement assets and internal/external metrics (including the degree to which methodology performance classification outcomes conform to national expert opinion). The results from the experiment confirm an accurate and computationally inexpensive methodology, which provides outcomes that compare to real-world pavement condition rating metrics.     

On partitions of functions on finite sets

Let D and R be finite sets with cardinality n and m respectivelyR ^D be the set of all functions from D into R, and G and H be permutation groups acting on D and R respectively. Two functions f and g in R ^D are said to be related if there exists a σ in G and a τ in H with f(σd) = τg(d) for every d in D. Since the relation is an equivalence relation, R ^D is partitioned into disjoint classes. Roughly, by using the cycle indices of G and H, de Bruijn's theorem determines the number of equivalence classes, and Pólya's theorem, with H being the identity group, gives the function counting series, Pólya-de Bruijn's theorem has many applications (for instance, see Pólya and Read [6]). The theorem and its applications, basically, centered around the partitions of functions. Here, we present an algorithm to determine which functions in R ^D belong to the same equivalent class. Our algorithm does not use the cycle indices of G and H (to compute the cycle index of a given group, in general, is difficult), but it uses the generators of G and H, and the m-nary numbers to code the functions in R ^D . Our algorithm also gives the function counting series and the number of equivalence classes. An important application is that for each positive integer n, we use our algorithm and the symmetric group S _n to determine all isomorphic and nonisomorphic graphs and directed graphs with n vertices.     

视频序列中基于头肩分割的人体位姿估计算法

当前常用3维重构的方法表示和计算视频中的人体位姿,但由于这些方法通常需要多个摄像头,不仅限制条件多,且计算复杂度高,为此,提出了一种基于头肩分割的人体位姿估计算法。该算法首先对视频中的人体进行头肩定位;然后利用人体头部的平面成像特点计算头部位姿,同时利用人体肩部的轮廓变化特点计算躯干位姿;最后结合头部和躯干的位姿估计运动中的人体位姿。实验结果证明,该算法是有效和优越的。     

信息的量化与联合作战模拟中武器装备作战能力指数

运用现有各种指数方法定量分析联合作战模拟中武器装备的作战能力时,描述的效果不能令人满意,需要构造新的能够统一描述联合作战模拟中武器装备作战能力的指数模型。该文首先简单介绍了熵理论和信息的量化。然后根据相似原理,分析了离散信源与武器装备之间的相似性,为构造联合作战模拟中武器装备作战能力指效进行了理论上的探讨。     

On the Identifiability of Finite Mixtures Based on the Union of Logarithmic Series and Discrete Rectangular Families

In this paper, finite mixtures of the union of Logarithmic Series and Discrete Rectangular families are proved to be identifiable. The sufficient condition for the identifiability of finite mixtures given by Atienza et al. (Metrika 63:215–221, 2006) is applied instead of mostly used Teicher’s condition (Teicher, Ann Math Stat 34: 1265–1269, 1963). The choice of distribution is made in order to stress the fact that, contrarily to Teicher’s approach, Atienza et al.’s theorem being used does apply to heterogeneous parametric families.