On the number of frames in binary words

A frame is a square uu, where u is an unbordered word. Let F(n) denote the maximum number of distinct frames in a binary word of length n. We count this number for small values of n and show that F(n) is at most ⌊n/2⌋+8 for all n and greater than 7n/30−? for any positive ? and infinitely many n. We also show that Fibonacci words, which are known to contain plenty of distinct squares, have only a few frames. Moreover, by modifying the Thue-Morse word, we prove that the minimum number of occurrences of frames in a word of length n is ⌈n/2⌉−2.     

On the number of higher order Delaunay triangulations

Higher order Delaunay triangulations are a generalization of the Delaunay triangulation that provides a class of well-shaped triangulations, over which extra criteria can be optimized. A triangulation is order-k Delaunay if the circumcircle of each triangle of the triangulation contains at most k points. In this paper we study lower and upper bounds on the number of higher order Delaunay triangulations, as well as their expected number for randomly distributed points. We show that arbitrarily large point sets can have a single higher order Delaunay triangulation, even for large orders, whereas for first order Delaunay triangulations, the maximum number is 2ⁿ⁻³. Next we show that uniformly distributed points have an expected number of at least 2^{ρ₁n(1+o(1))} first order Delaunay triangulations, where ρ₁ is an analytically defined constant (ρ₁≈0.525785), and for k>1, the expected number of order-k Delaunay triangulations (which are not order-i for any i<k) is at least 2^{ρ_kn(1+o(1))}, where ρ_k can be calculated numerically.     

On a special class of primitive words

When representing DNA molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its Watson-Crick complement θ(u), where θ denotes the Watson-Crick complementarity function. Thus, an expression which involves only a word u and its complement can be still considered as a repeating sequence. In this context, we define and investigate the properties of a special class of primitive words, called pseudo-primitive words relative to θ or simply θ-primitive words, which cannot be expressed as such repeating sequences. For instance, we prove the existence of a unique θ-primitive root of a given word, and we give some constraints forcing two distinct words to share their θ-primitive root. Also, we present an extension of the well-known Fine and Wilf theorem, for which we give an optimal bound.     

On the independence number and Hamiltonicity of uniform random intersection graphs

In the uniform random intersection graphs model, denoted by G_n,m,λ, to each vertex v we assign exactly λ randomly chosen labels of some label set M of m labels and we connect every pair of vertices that has at least one label in common. In this model, we estimate the independence number α(G_n,m,λ), for the wide range m=⌊n^α⌋,α<1 and λ=O(m^1/4). We also prove the Hamiltonicity of this model by an interesting combinatorial construction. Finally, we give a brief note concerning the independence number of G_n,m,p random intersection graphs, in which each vertex chooses labels with probability p.     

A method for the transformation of factors in factor analysis

A method is proposed for obtaining combinations of factors derived from a factor analysis characterized by a large number of near-zero loadings relative to the original variables. It differs from rotation of factors, which replaces r factors by an equal number, r, of differently oriented factors, in that each solution consists of a single direction in F variable space.     

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.     

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.     

On the Weighted Mean of a Pair of Strings

String matching and string edit distance are fundamental concepts in structural pattern recognition. In this paper, the weighted mean of a pair of strings is introduced. Given two strings, x and y, where d(x, y) is the edit distance of x and y, the weighted mean of x and y is a string z that has edit distances d(x, z) and d(z, y)to x and y, respectively, such that d(x, z) _ d(z, y) = d(x, y). We’ll show formal properties of the weighted mean, describe a procedure for its computation, and give practical examples. Received: 26 October 2000, Received in revised form: 27 April 2001, Accepted: 20 July 2001     

Automatic pronunciation scoring of words and sentences independent from the non-native’s first language

This paper describes an approach for automatic scoring of pronunciation quality for non-native speech. It is applicable regardless of the foreign language student’s mother tongue. Sentences and words are considered as scoring units. Additionally, mispronunciation and phoneme confusion statistics for the target language phoneme set are derived from human annotations and word level scoring results using a Markov chain model of mispronunciation detection. The proposed methods can be employed for building a part of the scoring module of a system for computer assisted pronunciation training (CAPT). Methods from pattern and speech recognition are applied to develop appropriate feature sets for sentence and word level scoring. Besides features well-known from and approved in previous research, e.g. phoneme accuracy, posterior score, duration score and recognition accuracy, new features such as high-level phoneme confidence measures are identified. The proposed method is evaluated with native English speech, non-native English speech from German, French, Japanese, Indonesian and Chinese adults and non-native speech from German school children. The speech data are annotated with tags for mispronounced words and sentence level ratings by native English teachers. Experimental results show, that the reliability of automatic sentence level scoring by the system is almost as high as the average human evaluator. Furthermore, a good performance for detecting mispronounced words is achieved. In a validation experiment, it could also be verified, that the system gives the highest pronunciation quality scores to 90% of native speakers’ utterances. Automatic error diagnosis based on a automatically derived phoneme mispronunciation statistic showed reasonable results for five non-native speaker groups. The statistics can be exploited in order to provide the non-native feedback on mispronounced phonemes.     

On the use of words and fuzzy sets

This paper only tries to stimulate some reflections, by showing a possible way towards rethinking fuzzy sets from their roots. A rethinking that does not change the view that fuzzy sets are mathematical entities giving extension to predicates. In such a way that, if the predicates are precise, the corresponding new entities are nothing else than classical sets.What, perhaps, is a key idea is that the use of a predicate organizes, in some way, the universe of discourse. When this organization is a preorder, the extension or L-set, appears once a degree, numerical or not, but consistent with the organization, can be defined.The ultimate goal of those above mentioned reflections, provided they would be realized in the future, is to extend the current theories of fuzzy sets to wider areas of both language and reasoning. Our objective is to reach a better knowledge of the links between language and its representations for the progress of computing with words and perceptions.     

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.     

On the growth rate of words in generalized Thue-Morse sequence

The paper summarizes properties of the pattern complexity for the generalized Thue-Morse sequence T and the sequence entropy of shift X_T generated by that sequence. We give the exact value of the pattern complexity and prove that the value of sequence entropy h_∞(X_T) is always bounded by log 4. In the second part we deal with the special case of T defined by the constant sequence and we find an upper bounding on the value of h_∞(X_T). The last theorem joins the properties of the shift X_T with odometers and shows an odometer G_s where X_T is at most 4-to-1 extension of.     

On quasi orders of words and the confluence property

We investigate the confluence property, that is, the property of a language to contain, for any two words of it, one which is bigger, with respect to a given quasi order on the respective free monoid, than each of the former two. This property is investigated mainly for regular and context-free languages. As a consequence of our study, we give an answer to an old open problem raised by Haines concerning the effective regularity of the sets of subwords. Namely, we prove that there are families with a decidable emptiness problem for which the regularity of the sets of subwords is not effective.     

AutoCAD图形插入Word中线宽和文本方向的控制

讨论了AutoCAD图形用几种方法插入到Word中图形线宽和文本方向的控制,对几种插图方法作了比较,对层的概念进行分析,找到了一种最佳方法来编辑线宽和文本,编辑完后对图形的缩放不影响线宽,提高了插图的质量。为书籍、期刊编排人员和科技论文的作者提供了参考。     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

On the number of broadcast schemes in networks

Broadcasting is the process of spreading one piece of information among a group of individuals connected by an interconnection network. In this paper we give exact lower and upper bounds for the number of broadcast schemes in arbitrary networks. Also, we give the exact value for complete bipartite graphs and an upper bound for regular networks. Based on the counting method we describe a new random algorithm for broadcasting in networks.