Search

In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number \(r\,\in \,]0,2]\), it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-known families of binary words.

The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of "clustering" together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet a, b having at most four b's and those having at most four a's.

In this paper we focus on the decomposition of rational and maximal prefix codes. We present an effective procedure that allows us to decide whether such a code is decomposable. In this case, the procedure also produces the factors of some of its decompositions. We also give partial results on the problem of deciding whether a rational maximal prefix code decomposes over a finite prefix code.

The objective of this paper is to study, by new formal methods, the notion of tree code introduced by Nivat in (Tree Automata and Languages, Elsevier, Amsterdam, 1992, pp. 1–19). In particular, we consider the notion of stability for sets of trees closed under concatenation. This allows us to give a characterization of tree codes which is very close to the algebraic characterization of word codes in terms of free monoids. We further define the stable hull of a set of trees and derive a defect theorem for trees, which generalizes the analogous result for words. As a consequence, we obtain some properties of tree codes having two elements. Moreover, we propose a new algorithm to test whether a finite set of trees is a tree code. The running time of the algorithm is polynomial in the size of the input. We also introduce the notion of tree equation as complementary view to tree codes. The main problem emerging in this approach is to decide the satisfiability of tree equations: it is a special case of second-order unification, and it remains still open.

In this paper we generalize an encoding method due to Girod (cf. [6]) using prefix codes, that allows a bidirectional decoding of the encoded messages. In particular we generalize it to any finite alphabet A, to any operation defined on A, to any code with finite deciphering delay and to any key x ∈ A+ , on a length depending on the deciphering delay. We moreover define, as in [4], a deterministic transducer for such generalized method. We prove that, fixed a code X ∈ A* with finite deciphering delay and a key x ∈ A *, the transducers associated to different operations are isomorphic as unlabelled graphs. We also prove that, for a fixed code X with finite deciphering delay, transducers associated to different keys have an isomorphic non trivial strongly connected component.

In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [ IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X . We find some bounds of such a number of states in relation with different notions of “size” of X . In particular, we give an exact formula for the number of states of transducers associated to maximal prefix codes. We moreover consider two special cases of codes: maximal uniform codes and a class of codes, that we name string-codes. We show that they represent, for maximal codes, the extreme cases with regard to the number of states in terms of different sizes. Moreover we prove that prefix codes corresponding to isomorphic trees have transducers that are isomorphic as unlabeled graphs.

We describe and highlight a generalization of the Burrows–Wheeler Transform (bwt) to a multiset of words. The extended transformation, denoted by ebwt, is reversible. Moreover, it allows to define a bijection between the words over a finite alphabet A and the finite multisets of conjugacy classes of primitive words in A∗. Besides its mathematical interest, the extended transform can be useful for applications in the context of string processing. In the last part of this paper we illustrate one such application, providing a similarity measure between sequences based on ebwt.

We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However, as we show, the prefix rank forms an exception.

We consider the iterates of bilinear functions over the semiring (max, +). Equivalently, our object of study can be viewed as recognizable tree series over the semiring (max, +). In this semiring, a fundamental result associates the asymptotic behaviour of the iterates of a linear function with the maximal average weight of the circuits in a graph naturally associated with the function. Here we provide an analog for the 'iterates' of bilinear functions. We also give a triple recognizing the formal power series of the worst case behaviour. Remark. Due to space limitations, the proofs have been omitted. A full version can be obtained from the authors on request.

We introduce the notion of equation on trees, generalizing the corresponding notion for words, and we develop the first steps of a theory of tree equations. The main result of the paper states that, if a pair of trees is the solution of a tree equation with two indeterminates, then the two trees are both powers of the same tree. As an application, we show that a tree can be expressed in a unique way as a power of a primitive tree. This extends a basic result of combinatorics on words to trees. Some open problems are finally proposed.

We introduce the notion of periodicity for k -ary labeled trees: roughly speaking, a tree is periodic if it can be obtained by a sequence of concatenations of a smaller tree plus a “remainder”. The period is the shape of such smaller tree (i.e. the corresponding unlabeled tree). This definition reduces to the classical one for string when restricted to the case of unary trees. Then, we define the greatest common divisor of two unlabeled trees and relate right congruences to unlabeled trees. This allows us to give a characterization of tree periodicity in terms of right congruences and then to prove a periodicity theorem for trees that is a generalization to trees of the Fine and Wilf's periodicity theorem for words.