Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

4 Fundamenta Informaticae

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On the Shuffle of Star-Free Languages

100%

Castiglione G. , Restivo A.

Fundamenta Informaticae

2012

tom Vol. 116, nr 1-4

35-44

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 starfree. Some of the special cases here approached give rise to new problems in combinatorics on words.

Higman's Theorem on Discrete Sets

80%

Burderi F. , Castiglione G. , Restivo A.

Fundamenta Informaticae

2006

tom Vol. 74, nr 4

435-446

In this paper we investigate properties of different classes of discrete sets with respect to the partial-order of subpicture. In particular we take in consideration the classes of convex polyominoes and L-convex polyominoes. In the first part of the paper we study closure properties of these classes with respect the order and we give a new characterization of L-convex polyominoes. In the second part we pose the question to extend Higman's theorem to discrete sets. We give a negative answer in the general case and we prove that the set of L-convex polyominoes is well-partially-ordered by using a representation of L-convex polyominoes in terms of words of a regular language.

On Fixed Points of the Burrows-Wheeler Transform

70%

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

Fundamenta Informaticae

2017

tom Vol. 154, nr 1/4

277--288

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.

Computing forbidden words of regular languages

70%

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

Fundamenta Informaticae

2003

tom Vol. 56, nr 1,2

121-135

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.