Modern Aspects of Complexity of Formal Languages

形式语言是理论计算机科学的基础领域之一。计算机科学应用的许多方面都可以用这个领域出现的思想工具来建模。许多算法问题也可以在这里公式化。 形式语言可以追溯到大约60年的历史。尽管如此，有相当数量的悬而未决的问题，往往组合的性质，例如猜想的切尔尼。这些问题中的大多数现在看来可能是“经典的”，这可能是近年来随着一些新的复杂性理论概念的出现，这些问题在很大程度上被忽视的原因之一，例如，越来越多的NP难问题（被认为是计算上不可行的）已被归类为属于参数化复杂性类FPT（具有适当的参数定义），这将意味着它们可以针对小参数有效地求解。类似地，考虑这样的NP难问题是否可能允许亚指数精确算法（或者这是否与指数时间假设（ETH）相矛盾）。另一个最近的研究领域是所谓的细粒度的复杂性，允许表明某些多项式时间算法是最佳的多对数因子。所有这些类型的研究都很好地代表了在计算理论中的所有国际事件，但很少应用于形式语言的问题。这个项目的总体目标应该是将复杂性理论的现代方法应用于源于自动机理论的问题，更广泛地说，源于形式语言的问题，因为这些经典领域仍然是理论计算机科学的支柱，许多底层算法在实践中得到了广泛应用。让我们提及编译器构造、文本编辑器、数据压缩和搜索引擎作为可能的应用领域。

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.