Wyniki wyszukiwania - BazTech

1

On Fixed Points of the Burrows-Wheeler Transform

Mantaci S., Restivo A., Rosone G., Russo F., Sciortino M.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

277--288

EN

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.

2

Epichristoffel Words and Minimization of Moore Automata

Castiglione G., Sciortino M.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 3/4

319--333

EN

This paper is focused on the connection between the combinatorics of words and minimization of automata. The three main ingredients are the epichristoffel words, Moore automata and a variant of Hopcroft’s algorithm for their minimization. Epichristoffel words defined in [14] generalize some properties of circular sturmian words. Here we prove a factorization property and the existence of the reduction tree, that uniquely identifies the structure of the word. Furthermore, in the paper we investigate the problem of the minimization of Moore automata by defining a variant of Hopcroft’s minimization algorithm. The use of this variant makes simpler the computation of the running time and consequently the study of families of automata that represent the extremal cases of the minimization process. Indeed, such a variant allows to use the above mentioned factorization property of the epichristoffel words and their reduction trees in order to find an infinite family of Moore automata such that the execution of the algorithm is uniquely determined and tight.

3

Computing forbidden words of regular languages

Béal M-P., Crochemore M., Mignosi F., Restivo A., Sciortino M.

Fundamenta Informaticae

|

2003

|

Vol. 56, nr 1,2

121-135

EN

We give a quadratic-time algorithm to compute the set of minimal forbidden words of a factorial regular language. We give a linear-time algorithm to compute the minimal forbidden words of a finite set of words. This extends a previous result given for the case of a single word only. We also give quadratic-time algorithms to check whether a regular language is factorial or anti-factorial.