Extending Parikh matrices

We introduce the notion of Parikh matrix induced by a word, a natural extension to the notion of Parikh matrix and prove a set of properties for this kind of matrices.

We also study the relation between these two notions. We show that combining properties from both we obtain a more powerful tool for proving algebraic properties of words.     

Enriching Parikh matrix mappings

In this paper, we define the Super-Parikh (S-Parikh) matrix mapping as an extension of the Parikh matrix mapping introduced by Mateescu et al. Like the Parikh matrix, the extension revolves around a certain type of square matrices, but instead of non-negative integers, its matrix-mapped elements are non-negative rationals (fractions). We study the basic properties of the newly defined formalism and later on we investigate the injectivity of the mapping. Also, we begin a search for the reverse mapping – that is a method for obtaining a word, given the S-Parikh matrix.     

Some characterizations of Parikh matrix equivalent binary words

We state different characterizations of pair of words having the same Parikh matrix.     

Minimal zero words for second-order matrices

An exact estimate is given for the length of a minimal zero word (sequence). This estimate equals q+2 for second-order matrices over a finite field GF(q). The correspondence problem is proved to be undecidable for matrices with rational elements. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 10–18, July–August 2007.     

用于DNA编码的部分字

寻找合理的DNA编码是DNA计算中一个基本的问题.因此要给出一种方法使得DNA序列不会产生不想要的结构,尤其是假阳性是解决此问题的关键.传统方法是要求码字间的Hamming距离足够大.因此考虑用部分字的方法来解决DNA编码问题,利用部分字的洞的定义及其性质得到了关于部分字的洞、Hamming距离和Watson-CrickHamming距离的3个命题,通过部分字对DNA编码进行了优化,解决了DNA编码中的部分疑难问题.     

纠错码和秩距离码的一些新的构造方法

给出一般纠错码和秩距离码的一些新的构造方法,求出了构造的各种码的生成矩阵。指出了最大秩距离Reed-Solomon码和最大秩距离BCH码为新构造的秩距离码的特殊情况。     

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.     

Semi-tensor product of matrices and its application to Morgen's problem

This paper proposes a new matrix product, namely, semi-tensor product. It is a general-ization of the conventional matrix product. Meanwhile, it is also closely related to Kronecker (tensor) product of matrices. The purpose of introducing this product is twofold: (i) treat multi-dimensional da-ta; (ii) treat nonlinear problems in a linear way. Then the computer and numerical methods can be easily used for solving nonlinear problems. Properties and formulas are deduced. As an application, the Morgan's problem for control systems is formulated as a numerically solvable problem.     

An automatic filtering method for field association words by deleting unnecessary words

Document classification and summarization are very important for document text retrieval. Generally, humans can recognize fields such as ?Sports? or ?Politics? based on specific words called Field Association (FA) words in those document fields. The traditional method causes misleading redundant words (unnecessary words) to be registered because the quality of the resulting FA words depends on learning data pre-classified by hand. Therefore recall and precision of document classification are degraded if the classified fields classified by hand are ambiguous. We propose two criteria: deleting unnecessary words with low frequencies, and deleting unnecessary words using category information. Moreover, using the proposed criteria unnecessary words can be deleted from the FA words dictionary created by the traditional method. Experimental results showed that 25% of 38 372 FA word candidates were identified as unnecessary and deleted automatically when the presented method was used. Furthermore, precision and F-measure were improved by 26% and 15%, respectively, compared with the traditional method.     

Periodic musical sequences and Lyndon words

When one enumerates periodic musical structures, the computation is done up to a cyclic shift. This means that two solutions which are cyclic shifts of one another are considered the same. Lyndon words provide a powerful way to do so. We illustrate this by two examples taken from African traditional music.     

Polynomial approximation of functions of matrices and applications

In solving a mathematical problem numerically, we frequently need to operate on a vector by an operator that can be expressed asf(A), whereA is anN ×N matrix [e.g., exp(A), sin(A), A^–-]. Except for very simple matrices, it is impractical to construct the matrixf (A) explicitly. Usually an approximation to it is used. This paper develops an algorithm based upon a polynomial approximation tof (A). First the problem is reduced to a problem of approximatingf (z) by a polynomial in z, where z belongs to a domainD in the complex plane that includes all the eigenvalues ofA. This approximation problem is treated by interpolatingf (z) in a certain set of points that is known to have some maximal properties. The approximation thus achieved is almost best. Implementing the algorithm to some practical problems is described. Since a solution to a linear systemAx=b isx=A ^–1 b, an iterative solution algorithm can be based upon a polynomial approximation tof (A)=A ^–1. We give special attention to this important problem.     

A note on the Markoff condition and central words

We define Markoff words as certain factors appearing in bi-infinite words satisfying the Markoff condition. We prove that these words coincide with central words, yielding a new characterization of Christoffel words.     

Block TERM factorization of block matrices

Duetothelimitationofcomputationalprecisionandstoragecapacity,transformsusedinlosslessdatacompressionshouldbeequivalentlyinteger-reversible.Reversibleintegertransform(orintegermapping)issuchatypeoftransformthatmapsintegerstointegersandrealizesperfectreconstruction(PR).Peoplestartedtoworkinthisarealongago,andtheirearlywork,suchasStransform[1],TStransform[2],S+Ptransform[3],andcolorspacetransforms[4],suggestedapromisingfutureofreversibleintegermappinginimagecompression,region-of-interest(ROI)…     

Color texture classification by integrative Co-occurrence matrices

Integrative Co-occurrence matrices are introduced as novel features for color texture classification. The extended Co-occurrence notation allows the comparison between integrative and parallel color texture concepts. The information profit of the new matrices is shown quantitatively using the Kolmogorov distance and by extensive classification experiments on two datasets. Applying them to the RGB and the LUV color space the combined color and intensity textures are studied and the existence of intensity independent pure color patterns is demonstrated. The results are compared with two baselines: gray-scale texture analysis and color histogram analysis. The novel features improve the classification results up to 20% and 32% for the first and second baseline, respectively.     

On stabilizers of infinite words

The stabilizer of an infinite word over a finite alphabet Σ is the monoid of morphisms over Σ that fix . In this paper we study various problems related to stabilizers and their generators. We show that over a binary alphabet, there exist stabilizers with at least n generators for all n. Over a ternary alphabet, the monoid of morphisms generating a given infinite word by iteration can be infinitely generated, even when the word is generated by iterating an invertible primitive morphism. Stabilizers of strict epistandard words are cyclic when non-trivial, while stabilizers of ultimately strict epistandard words are always non-trivial. For this latter family of words, we give a characterization of stabilizer elements.     

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].