Modern Aspects of Complexity of Formal Languages

点击翻译按钮获取中文摘要

Formal Languages are one of the basic areas of Theoretical Computer Science. Many aspects of applications of computer science can be modeled with ideas tools emerging from this area. Many algorithmic questions can be formulated here, as well. Formal Languages can look back at a history of about 60 years. Nonetheless, there are quite a number of unresolved questions, often combinatorial in nature, as for instance the conjecture of Cerny. Most of these questions may look "classical" now, which might be one of the reasons why these problems have been largely neglected in recent years, when several new complexity theoretic concepts emerged.For instance, more and more NP-hard problems (that are thought to be computationally infeasible) have been classified to belong to the parameterized complexity class FPT (with appropriate definitions of parameter), which would mean that they could be efficiently solved for small parameters. Similarly, it was considered if such NP-hard problems might allow subexponential exact algorithms (or if this would contradict the exponential time hypothesis (ETH)). Another recent research area is the so-called fine-grained complexity that allows to show that certain polynomial-time algorithms are optimal up to polylogarithmic factors. All these types of research are well represented at all international events of high esteem in the theory of computing, but rarely applied to problems in Formal Languages. This should be changed with our new project.The overall aim of this project should be to apply these modern methods of complexity theory to problems originating from automata theory and, more generally, from formal languages, because these classical areas are still the backbone of Theoretical Computer Science and many of the underlying algorithms are widely applied in practice. Let us mention compiler construction, text editors, data compression and search engines as possible application areas.