Quasiperiodic Sturmian words and morphisms

We characterize all quasiperiodic Sturmian words: A Sturmian word is not quasiperiodic if and only if it is a Lyndon word. Moreover, we study links between Sturmian morphisms and quasiperiodicity.     

On the structure of bispecial Sturmian words

A balanced word is one in which any two factors of the same length contain the same number of each letter of the alphabet up to one. Finite binary balanced words are called Sturmian words. A Sturmian word is bispecial if it can be extended to the left and to the right with both letters remaining a Sturmian word. There is a deep relation between bispecial Sturmian words and Christoffel words, that are the digital approximations of Euclidean segments in the plane. In 1997, J. Berstel and A. de Luca proved that palindromic bispecial Sturmian words are precisely the maximal internal factors of primitive Christoffel words. We extend this result by showing that bispecial Sturmian words are precisely the maximal internal factors of all Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the language of Sturmian words.     

Conjugacy of morphisms and Lyndon decomposition of standard Sturmian words

Using the notions of conjugacy of morphisms and of morphisms preserving Lyndon words, we answer a question of G. Melançon. We characterize cases where the sequence of Lyndon words in the Lyndon factorization of a standard Sturmian word is morphic. In each possible case, the corresponding morphism is given.     

On the arithmetical complexity of Sturmian words

Using the geometric dual technique by Berstel and Pocchiola, we give a uniform O(n³)$O\left(n^3\right)$ upper bound for the arithmetical complexity of a Sturmian word. We also give explicit expressions for the arithmetical complexity of Sturmian words of slope between 1/3 and 2/3 (in particular, of the Fibonacci word). In this case, the difference between the genuine arithmetical complexity function and our upper bound is bounded, and ultimately 2-periodic. In fact, our formula is valid not only for Sturmian words but for rotation words from a wider class.     

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.     

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.     

超像素词包模型与SVM分类的图像标注

为了改善基于词包模型与支持向量机(SVM)分类一幅图对应一个标签的单标签分类问题,提出了一种基于超像素词包模型与SVM分类的图像标注算法.将超像素分割结果作为词包模型的基本单元,用词包模型生成的视觉词汇表示超像素区域特征,保留了图像中的同质区域,很好地利用了图像的区域特征.仿真结果表明,该方法能有效改善基于词包模型与SVM分类的单标签分类问题,且分类的准确性有所提高.     

Estimation of the length of reset words for automata with simple idempotents

A quadratic upper bound on the length of a minimal reset word is obtained for finite automata with simple idempotents. Each input symbol of the automata considered induces a transformation that is an idempotent with the unit defect or a bijection on the set of states. This bound is only twice as large as the well-known lower bound of this length. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 32–39, May–June, 2000.     

HEp-2 image classification using intensity order pooling based features and bag of words

Human Epithelial type 2 (HEp-2) cells play an important role in the diagnosis of autoimmune disorder. Traditional approach relies on specialists to observe HEp-2 slides via the fluorescence microscope, which suffers from a number of shortcomings like being subjective and labor intensive. Pattern recognition techniques have been recently introduced to this research issue to make the process automatic. However, performances of current systems available in literature are not satisfying. We propose in this paper a framework using intensity order pooling based gradient feature and bag of words for HEp-2 classification. By pooling the gradient features based on the intensity orders of local grid points, the pooled feature is rotationally invariant without requirement of orientation estimation. The proposed approach was fully tested using publicly available ICPR dataset and our own SZU dataset. Experimental results show that the propose method significantly outperformed widely used SIFT feature and the winner of ICPR contest 2012. Encouraging 100% image level accuracy was achieved on the SZU dataset.     

Relation between spinal load factors and the high-risk probability of occupational low-back disorder

Spinal compression is traditionally assumed the principal biomechanical mechanism associated with occupationally related low-back disorders (LBD). However, there is little conclusive evidence demonstrating that compression is related to occupational LBD. The objective of this research was to examine whether axial compression in the lumbar spine can predict the probability that a lifting task should be classified as high risk for LBD. Furthermore, the improvement in predictive ability was examined when analyses include 3-D, dynamic biomechanical factors. Ten experienced warehouse workers transferred 12 pallet loads of boxes in a simulation of warehouse working conditions. Biomechanical estimates of 2-D static and 3-D dynamic spinal compression, shear loads and tissue strains were achieved from the subjects during each lifting exertion. Each lift was also assessed for probability of high LBD risk classification. Regression analyses were performed to examine the relationship between biomechanical and epidemiological factors. Results indicate 2-D static estimates of spinal compression describe ? 13% of the probability of high LBD risk variability. Dynamic estimates of spinal compression describe >44% of the variability. A multifactor regression model including 3-D spinal loads and tissue strains further improved the predictive ability, but the improvement was not statistically significant. This research demonstrates the biomechanical source of low-back pain is dynamic, multifaceted and multidimensional. Significant improvements in ergonomics assessments can be achieved by examining interactions of dynamic biomechanical factors. Unfortunately, this improved predictive ability is generated at the high cost of computational complexity. However, less realistic biomechanical representations may ignore the injury mechanisms associated with the greater number of workplace injuries. Thus, improved understanding of the dynamic biomechanical interactions influencing the tolerance and injury mechanisms of the spine may permit more accurate assessments of workplace injury factors associated with LBD and reduced incidence of occupationally related low-back pain.     

Relation between spinal load factors and the high-risk probability of occupational low-back disorder.

Spinal compression is traditionally assumed the principal biomechanical mechanism associated with occupationally related low-back disorders (LBD). However, there is little conclusive evidence demonstrating that compression is related to occupational LBD. The objective of this research was to examine whether axial compression in the lumbar spine can predict the probability that a lifting task should be classified as high risk for LBD. Furthermore, the improvement in predictive ability was examined when analyses include 3-D, dynamic biomechanical factors. Ten experienced warehouse workers transferred 12 pallet loads of boxes in a simulation of warehouse working conditions. Biomechanical estimates of 2-D static and 3-D dynamic spinal compression, shear loads and tissue strains were achieved from the subjects during each lifting exertion. Each lift was also assessed for probability of high LBD risk classification. Regression analyses were performed to examine the relationship between biomechanical and epidemiological factors. Results indicate 2-D static estimates of spinal compression describe approximately 13% of the probability of high LBD risk variability. Dynamic estimates of spinal compression describe > 44% of the variability. A multifactor regression model including 3-D spinal loads and tissue strains further improved the predictive ability, but the improvement was not statistically significant. This research demonstrates the biomechanical source of low-back pain is dynamic, multifaceted and multidimensional. Significant improvements in ergonomics assessments can be achieved by examining interactions of dynamic biomechanical factors. Unfortunately, this improved predictive ability is generated at the high cost of computational complexity. However, less realistic biomechanical representations may ignore the injury mechanisms associated with the greater number of workplace injuries. Thus, improved understanding of the dynamic biomechanical interactions influencing the tolerance and injury mechanisms of the spine may permit more accurate assessments of workplace injury factors associated with LBD and reduced incidence of occupationally related low-back pain.     

Inconstancy of finite and infinite sequences

In order to study large variations or fluctuations of finite or infinite sequences (time series), we bring to light an 1868 paper of Crofton and the (Cauchy-)Crofton theorem. After surveying occurrences of this result in the literature, we introduce the inconstancy of a sequence and we show why it seems more pertinent than other criteria for measuring its variational complexity. We also compute the inconstancy of classical binary sequences including some automatic sequences and Sturmian sequences.     

藏文文本中格助词的识别研究简

藏文信息处理中要对自然语言进行理解并生成且藏文格与语义有关,藏文格到目前为止都是研究者手动处理,而不是电脑处理,所以需开发出电脑替人自动识别格的软件是当前最急需研究的项目之一,从而藏文研究者和学习者可用此软件对藏文格进行自动识别,还能正确消除藏文语境歧义,而且在时间上、人力上都大大节省且提高了效率。本文通过研究藏文格的用法,建设藏文八格的知识库和藏文八格的算法及识别研究。     

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.     

API函数挂接的机理与方法探讨

介绍了在Windows的高级编程中所涉及的对Windows系统应用程序接口(API)函数的挂接的原理,并探讨了实现API函数挂接的条件。提供了几种实用的挂接方法(直接或间接修改API)及实现代码,给出了这些方法的不同适用场合。     

A new connection between quantum circuits,graphs and the Ising partition function

We present a simple construction that maps quantum circuits to graphs and vice-versa. Inspired by the results of D. A. Lidar linking the Ising partition function with quadratically signed weight enumerators (QWGTs), we also present a problem for the additive approximation of a function over hypergraphs related to the generating function of Eulerian subgraphs for ordinary graphs. Further, if E is an oracle that returns approximations of this function, we prove that P^E = BQP. We also discuss connections with the Ising partition function.