• Weconsider the problem of completing a Wheeler Deterministic Finite Automaton (WDFA) A, that is, of embedding A into an equivalent complete WDFA. • WedefineWheeler-complete automata and prove that there exists a unique minimal Wheeler complete DFA containing A: it is called the minimal Wheeler-completion of A. • Wegive an algorithm that, given as input a WDFA, returns its minimal Wheeler-completion. • We derive some interesting applications of this algorithm concerning the construction of a WDFA for the union and a WDFA for the complement of Wheeler languages. We consider the problem of embedding a Wheeler Deterministic Finite Automaton (WDFA, in short) into an equivalent complete WDFA, preserving the order of states and the accepted language. In some cases, such a complete WDFA does not exist. We say that a WDFA is Wheeler-complete (W-complete, in short) if it cannot be properly embedded into an equivalent WDFA. We give an algorithm that, given as input a WDFA A , returns the smallest W-complete DFA containing A : it is called the minimal W-completion of A . We derive some interesting applications of this algorithm concerning the construction of a WDFA for the union and a WDFA for the complement of Wheeler languages.

Abstract We extend the notion of the Dyck language from words to two-dimensional arrays of symbols, i.e., pictures, using the row-column combination (also known as the crossword) of two Dyck languages over the same alphabet. In a Dyck crossword picture, each column and each row must be a word from the respective Dyck language. The pairing of open and closed parentheses in a Dyck word can be represented by edges connecting corresponding cells in the same row or column. This defines a matching graph, which serves as the two-dimensional analogue of the syntactic tree of a Dyck word. A matching graph is partitioned into simple circuits of unbounded length (always a multiple of four), whose labels form a regular language. These circuits exhibit a wide variety of forms and labelings, which we illustrate and partially classify. With a two-letter alphabet, a Dyck crossword is necessarily empty. The minimal non-trivial case, requiring an alphabet of size four, already generates all possible forms of matching graphs and is the primary focus of our study. We prove that the only picture with a single matching circuit (i.e., a Hamiltonian cycle) has size 2 by 2. Two key properties of Dyck words–cancellation and well-nesting–can be generalized to two dimensions, leading to two alternative definitions of 2D Dyck languages: neutralizable and well-nested. These languages are special cases of Dyck crossword pictures called quaternate, where all circuits have length 4 (i.e., are rectangles). This results in a strict language inclusion hierarchy: well-nested $$\subset $$ ⊂ neutralizable $$\subset $$ ⊂ quaternate $$\subset $$ ⊂ Dyck crosswords. When the alphabet size exceeds four, not all combinations of row and column Dyck languages yield non-empty crosswords. To identify productive combinations, we introduce an alphabetic graph, where nodes represent alphabet symbols and edges represent their couplings. A matching circuit corresponds to the unrolling of an alphabetic graph circuit. Finally, we prove that Dyck crosswords are not tiling-recognizable, as expected for a definition extending Dyck word languages to pictures.

The row-column combination RCC maps two (word) languages over the same alphabet onto the set of rectangular arrays, i.e., pictures, such that each row/column is a word of the first/second language. The resulting array is thus a crossword of the component words. Depending on the family of the components, different picture (2D) language families are obtained: e.g., the well-known tiling-system recognizable languages are the alphabetic projection of the crossword of local (regular) languages. We investigate the effect of the RCC operation especially when the components are context-free, also with application of an alphabetic projection. The resulting 2D families are compared with others defined in the past. The classical characterization of context-free languages, known as Chomsky-Schützenberger theorem, is extended to the crosswords in this way: the projection of a context-free crossword is equivalent to the projection of the intersection of a 2D Dyck language and the crossword of strictly locally testable language. The definition of 2D Dyck language relies on a new more flexible so-called Cartesian RCC operation on Dyck languages. The proof involves the version of the Chomsky-Schützenberger theorem that is non-erasing and uses a grammar-independent alphabet.

Introduced about thirty years ago in the field of data compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance of memoryless compressors, plays a fundamental role in the design of efficient self-indexing compressed data structures. Finding other string transformations with the same remarkable properties of BWT has been a challenge for many researchers for a long time. Among the known BWT variants, the only one that has been recently shown to be a valid alternative to BWT is the Alternating BWT (ABWT), an invertible string transformation introduced about ten years ago in connection with a generalization of Lyndon words. In this paper, we introduce a whole class of new string transformations, called local orderings-based transformations, which have all the “myriad virtues” of BWT. We show that this new family is a special case of a much larger class of transformations, based on context adaptive alphabet orderings, that includes BWT and ABWT. Although all transformations support pattern search, we show that, in the general case, the transformations within our larger class may take quadratic time for inversion and pattern search. As a further result, we show that the local orderings-based transformations can be used for the construction of the recently introduced r-index, which makes them suitable also for highly repetitive collections. In this context, we consider the problem of finding, for a given string, the BWT variant that minimizes the number of runs in the transformed string, and we provide an algorithm solving this problem in linear time.

In this paper we investigate similarity measures based on minimal absent words, introduced by Chairungsee and Crochemore in [1]. They make use of a length-weighted index on a sample set corresponding to the symmetric difference M(x)ΔM(y) of the minimal absent words M(x) and M(y) of two sequences x and y, respectively. We first propose a variant of this measure by choosing as a sample set a proper subset 𝒟(x, y) of M(x)ΔM(y), which appears to be more appropriate for distinguishing x and y. From the algebraic point of view, we prove that 𝒟(x, y) is the base of the ideal generated by M(x)ΔM(y). We then remark that such measures are able to recognize whether the sequences x and y share a common structure, but they are not able to detect the difference on the number of occurrences of such a structure in the two sequences. In order to take into account such a multiplicity, we introduce the notion of multifactor, and define a new measure that uses both absent words and multifactors. Surprisingly, we prove that this similarity measure coincides with a distance on sequences introduced by Ehrenfeucht and Haussler in [2], in the context of block-moves strategies. In this way, our result creates a non trivial bridge between similarity measures based on absent words and those based on the block-moves approach.

In this paper we compare two finite words u and v by the lexicographical order of the infinite words u^omega and v^omega. Informally, we say that we compare u and v by the infinite order. We show several properties of Lyndon words expressed using this infinite order. The innovative aspect of this approach is that it allows to take into account also non trivial conditions on the prefixes of a word, instead that only on the suffixes. In particular, we derive a result of Ufnarovskij [V. Ufnarovskij, Combinatorial and asymptotic methods in algebra, 1995] that characterizes a Lyndon word as a word which is greater, with respect to the infinite order, than all its prefixes. Motivated by this result, we introduce the prefix standard permutation of a Lyndon word and the corresponding (left) Cartesian tree. We prove that the left Cartesian tree is equal to the left Lyndon tree, defined by the left standard factorization of Viennot [G. Viennot, Algèbres de Lie libres et monoïdes libres, 1978]. This result is dual with respect to a theorem of Hohlweg and Reutenauer [C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, 2003].

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 ad vantage 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.

Motivated by the general problem to characterize families of languages closed under shuffle, we investigate some conditions under which the shuffle of two star-free languages is star-free. Some of the special cases here approached give rise to new pr

Summary form only given. We introduce an extension of the Burrows-Wheeler transform to a multiset of primitive words. Primitiveness is not actually a restrictive hypothesis, since in practice almost all the processed texts are primitive (or become primitive by adding an end-of-string symbol). We prove that such a transformation as the BWT is reversible. We show how to use the transformation as a preprocessing for the simultaneous compression of different texts.

In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once. Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n+2) satisfies the rational recurrence relation fn =4fn−1 −2fn−2, with f0 =1, f1 =2, f2 =7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.

We give a new text-compression scheme based on forbidden words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. The techniques used in this paper are from information theory and finite automata.

The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove some closure properties with respect to different kinds of operations. From this, we derive that some natural families of two-dimensional languages (finite languages, regular languages, locally testable languages) are recognizable. Further we give some necessary conditions for recognizability which provides tools to show that certain languages are not recognizable. Although REC shares several properties of recognizable string languages, however, differently from the case of words, we prove here that REC is not closed under complementation and that the emptyness problem is undecidable for this family of languages. Finally, we report some characterizations of family REC by means of machine-based models and logic-based formalisms.

The purpose of this paper is to propose a new notion of recognizability for picture (two-dimensional) languages extending the characterization of one-dimensional recognizable languages in terms of local languages and alphabetic mappings. We first introduce the family of local picture languages (denoted by LOC) and, in particular, prove the undecidability of the emptiness problem. Then we define the new family of recognizable picture languages (denoted by REC). We study some combinatorial and language theoretic properties of REC such as ambiguity, closure properties or undecidability results. Finally we compare the family REC with the classical families of languages recognized by four-way automata.

In a recent paper A. Lempel (ibid., vol.IT-32, p.714-16, 1986) introduced the notion of a multiset decipherable (MSD) code to handle some special problems of information transmission. He showed that no MSD code contains a full prefix code as a proper subcode; he further conjectured that no MSD code contains a full uniquely decipherable code as a proper subcode and that every MSD code satisfies the Kraft inequality. A proof of the first conjecture and a disproof of the second are given.>