Summary
Automata theory (AT) is one of the longest established areas in Computer Science. Over the past few years, AT has not only developed in many different directions, but has also evolved in an exciting way at several levels: the exploration of specific new models and applications has at the same time stimulated a variety of deep mathematical theories. This project proposes a set of co-ordinated actions for advancing the theory of automata and for increasing its application to challenging scientific problems.
Standard applications of AT include pattern matching, syntax analysis and software verification. In recent years, novel applications of automata-theoretic concepts have emerged from biology, physics, cognitive sciences, neurosciences, control, tomography, linguistics, mathematics, etc., while developments in information technology have increased the need for formally-based design and verification methods to cope with such emerging technical needs as network security, mobile intelligent devices, and high performance computing.
At the same time, the mathematical foundations of AT rely on more and more advanced parts of mathematics. While, in the early sixties, only elementary graph theory and combinatorics were required, new tools from non-commutative algebra (semigroups, semirings and formal power series), logic, probability theory and symbolic dynamics have been successively introduced and the latest developments borrow ideas from topology and geometry.
Both trends have enhanced the role of fundamental research in AT and the importance of closer interaction between theoretical and applied scientists.
On one hand, significant advances in fundamental aspects of AT can be measured by recent progress on some deep open questions of the classical theory. On the other hand, new theoretical problems arise from applications and also from the sprouting of new automata models and generative devices, motivated by applications, which require a systematic investigation of their theoretical aspects.
Our project is a multidisciplinary programme at the crossroads of mathematics, theoretical computer science and applications. By setting up a framework where new applications of AT and theoretical insights can be communicated and shared by an open and qualified group of European scientists, this programme will catalyse progress in both directions. Specialized workshops, full conferences, schools for training young researchers and grants for short visits or exchanges will be our main tools for producing synergies between the main European teams in this domain.
Keywords. Automata, Semigroups, Formal grammars and languages, Combinatorics on words, Model Checking.
Duration
5 years : from May 2005 to May 2010
