|Thesis title:||Two contributions to Automata Theory on Parallelization and Data Compression|
|Advisor:||Stefano Crespi Reghizzi|
|Research area:||Advanced Software, Architectures and Methodologies|
The work presented in the Ph.D. thesis includes two main subjects developed independently in “Politecnico di Milano” and in “Université de Marne-la-Vallée”.
The first one deals with trace languages and in particular with the membership problem for trace languages. They are an interesting model for concurrent systems since a trace language is not a set of words but a set of classes of words. Some of the letters of the alphabet are indeed allowed to commute so that two distinct words can be equivalent because obtained one from the other with a sequence of permitted commutations.
A letter can be viewed as an instruction of a program; two instructions which are independent (i.e. they do not need to use the same registers) can be executed in parallel, or the order of their executions can be changed, that is, the letters representing them can commute.
The interest is focused on the membership problem for trace languages, with particular attention to the class of languages used to model programs executions. The recognition of a word reflects indeed the fact that the scheduling of a program represented by the word is acceptable.
The second subject is mainly about the Crochemore factorization of infinite words. The Crochemore factorization was introduced at the aim of constructing a linear algorithm for the detection of squares in texts. The definition of this factorization is very similar to the factorizations used by A. Lempel and J. Ziv in their well-known algorithms for data compression.
A first study involved the relationship between these factorizations in terms of countiong the number of factors.
The second part of the research treated the characterization of the Crochemore factorization of the main families of infinite words. It is in fact possible to provide directly these factorizations, which have very interesting connections with the combinatorial properties of the words.
Recently, these two subjects have been connected in new works, where it is investigated the compressibility of trace languages through the use of the Ziv-Lempel factorization.