Advances and Applications of Automata on Words and Trees

Summary

Automata theory is one of the longest established areas in computer science. Over the past few years, automata theory 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.

The insights developed in automata theory had a strong impact on numerous scientific areas. Standard applications include pattern matching, syntax analysis, foundations of XML, and hardware and software verification. In recent years, novel applications have emerged from biology, physics, cognitive sciences, neurosciences, control, tomography, linguistics, mathematics, etc. The new developments in information technology have increased the need for formally-based design and verification methods to cope with emerging technical challenges in network security, electronic business, mobile intelligent devices, and high performance computing.

At the same time, the mathematical foundations of automata theory 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 game theory, topology and geometry. Both trends have enhanced the role of fundamental research in automata theory and the importance of closer interaction between theoretical and applied scientists.

On the one hand, significant advances in fundamental aspects of automata theory 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.

The aim of the seminar was to discuss and systematize the recent fast progress in automata theory and to identify important directions for future research. For this, the seminar brought together more than 40 researchers from automata theory and related fields of applications. We had 19 talks of 30 minutes and 5 one-hour lectures, leaving ample room for discussions. The talks in this seminar ranged over a broad assortment of subjects with the underlying theme of automata on words and trees. It was a very fruitful seminar and has hopefully initiated new directions in research. We look forward to similar meetings in the future!