Modern Aspects of Complexity of Formal Languages

形式语言复杂性的现代方面

• 批准号: 407073110
• 负责人: Professor Dr. Henning Fernau
• 金额: --
• 依托单位: Max-Planck-Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/407073110?language=en
• 关键词: Modern; Aspects; Complexity; 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.

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