Aims of the research program

The aim of the project is to farther research in the sector of formal languages and automata (both for theoretical models and applications in specific fields) integrating the different expertise of the units participating in the project. More specifically, we plan to develop the research lines reported below. Each of these lines will be developed jointly by several research units.

Finite State Models: A first line of research will concern problems of design of unary quantum automata. A second line of research concerns a hierarchy of computational models, called quantum transductors, proposed as a starting point by several members of some units in the project. A further topic of research concerns the analysis of properties of hybrid automata, i.e. finite automata with restricted quantum components (memory registers of very few quantum bits). This activity will be completed by the study of conservative and reversible quantum gates for modal-intuitionistic multi value fuzzy logics. We also intend to develop applications of finite state models to problems of data compression, design of search engine for web documents and representation of dictionaries or finite languages.

Combinatorics on words and theory of codes: The research will follows several directions. The first one is concerned with problems in combinatorics on words that are motivated by the design of efficient algorithms of text compression and applications to molecular biology and molecular computing. This line will be developed by the joined contribution of several teams in the project. One of the main research subject concerns periodicity and the relationships between "local" and "global" periodicity, in a setting more general than that considered in the critical factorization theorem. We shall investigate combinatorial properties of word by using the notions of special factor, bispecial factor, box, minimal forbidden factor. Several ialgorithmic applications of these problems to molecular biology will be considered. As regards the theory of variable length codes, a first research line is to use ideas, notions, methods and results of Symbolic Dynamics to investigate open problems in the theory of codes and, in particular, problems concerning the length distribution. Another research line regards the fomous "factorization conjecture" that will be studied by investigating both the algebraic and combinatorial properties of codes and the unambiguous factorizations of languages.

Grammars: A first line of research concerns syntax of artificial languages and parsing, by using alternative methods with respect to context-free grammars as the already mentioned associative grammars. The investigation applies methods of local testability to the definition of tree and string languages. In a second line of research, we intend to examine and to compare the representation of regular languages by NSE grammars with other type of representations of regular languages. A third line of research concerns splicing systems and membrane systems. As far as we know, a characterization of languages generated by splicing systems referred to a circular form of DNA is unknown. We will study this problem under particular restrictions imposed on the system (hypothesis of finiteness of the set of the rules and axioms). Concerning membrane systems, we mean to introduce some variants (such as dynamics or polarizations of membranes) which are more biologically plausible, looking at the same time for stronger characterization results. Finally, research activity is proposed with focus on the ambiguity degree of context-free grammars, with a specific interest in characterizing sublinear ambiguity degrees.

Formal models of parallel and timed systems: We improve the study of recognizable and rational trace languages, with focus on the estimation of average trace height referred to Foata form which optimizes the parallelization. We study of machine code parallelization using description by rational trace languages. We focus on the theory and application of timed automata. Timed automata are suitable for specifying the temporal behaviour of real-time systems. We are interested in the study of the decidability and complexity properties of the time behaviour of such automata.

Bidimensional languages and images: The research activity concerns the generalizations of notions (like, for instance, periodicity, minimal forbidden factor, etc.) methods and results of combinatorics on words to structures more general than words, like trees and bidimensional words (images). The applications are in the area of image processing (in particular image compression) and in the area of cellular automata. We consider the construction of a "robust" theory for languages of infinite bidimensional words, generalizing at the same time the theory of regular omega-languages and the theory of regular bidimensional languages. We deal with discrete tomography, i.e. problems related to the reconstruction of a digital image from a set of projections.

Automata with resource constraints: A first research line carries on the investigation on the optimal costs of automata simulations. Particular attention will be paid to verify the applicability of the adopted techniques to the study of sublogarithmic complexity classes. A main open problem is the cost (in term of states) of the optimal simulation of two-way nondeterministic automata by two-way deterministic automata. Similar questions will be attacked in both probabilistic and quantistic cases, with the aim of capturing the descriptional power of every model. A further research line will be dealing with the study of the simulations between automata using several kinds of memories (stacks, queues, etc.).