PRIN Project - abstract

This project proposes a set of co-ordinated actions for advancing the theory of automata and its application to technological and scientific problems. Mathematical investigations will be concerned both with classical approaches such as combinatorics and semigroups, and with new conceptual tools from non-commutative algebra, logic, probability theory and symbolic dynamics.

Potential scientific applications include among others coding, biology, cognitive and neuro-sciences, compilation and software verification, web resources.

Interdisciplinary cooperation between mathematicians, theoretical computer scientists and engineers will allow synergy between fundamental research and study of new application driven formal models.

By setting up a framework where challenges from new applications of AT and theoretical insights can be communicated and shared by a qualified group of scientists and doctoral students, this programme will catalyse progress in both directions.

Avoiding dispersion over the entire field, a limited range of research directions will be pursued:

A1) Automata models, formal series, and their properties: Analysis of computational models such as quantum automata, analysis of their behaviours described by formal languages. Descriptional complexity of automata with bounded resources. Algebraic properties of finite automata, with focus on the study of inverse semigroups via automata. Analysis of properties of rational and holonomic formal series, with applications to pattern statistics, counting and random generation of words in languages of given classes.

A2) Codes, combinatorics on words and complex structures. Applications of combinatorics on words to Data Compression, Approximate string matching, Fragment Assembly Problem. Combinatorial, structural and arithmetic properties of the Sturmian words. Order properties of classes of structures such as paths, permutations, and set partitions; Enumerative problems of patterns avoiding permutations. Characterization of the factorizing codes by structural descriptions. Weaker decipherability conditions; variety of codes.

A3) Context-free grammars and unconventional representations for formal languages. XML-grammars and XML-languages. Improving classical constructions of syntax-directed translators for deterministic languages. New extensions of Higman's theorem. Fundamental and algorithmic problems of Associative Language Descriptions (ALD); open inclusion problem of regular and ALD languages. Characterization of regular languages generated by finite (linear or circular) splicing systems.

A4) Bidimensional languages and structures Study of recent formal models extending to 2D the classical Regular and Context-free definitions. More precisely, for Tiling Systems (TS) and Tile Rewriting Grammars (TRG), research on corresponding automata and parsing algorithms, relations with other models, generalization of regular expressions in 2D, characterization of unary languages, suitability to applications to image processing. Study of some extensions of L-convex polyominoes in the classical fields of investigations about polyominoes. A5) Formal models of distributed and timed systems Research on automata models suited to system verification and analysis, in particular on: Timed automata and extensions to unbounded memory machines such as stack equipped ones and dense counter timed automata; complexity issues relevant for model checking. Research on algorithms for code parallelization for programms represented by formal models, namely trace languages and by affine transformations.