Equations in groups, formal languages and complexity

解方程一直是数学的中心问题。无论是寻找多项式的根还是求解微分方程，寻找或近似解都是科学的重要组成部分，从纯粹到应用，理解解的性质打开了代数、动态、几何或逻辑结构的世界。该项目的核心是寻找和理解无限非abel离散群中的方程的解，这是一个在可解和不可解之间的前沿课题，在代数、逻辑、几何和理论计算机科学中具有深远的应用。理解解对于将代数几何扩展到非交换设置，掌握结构的一阶理论，确定两个双曲群之间的同构，推进统一理论以及回答有关单词组合的问题至关重要。尽管Makanin、Razborov、Sela、Kharlampovich、Miasnikov等人在这一领域做出了开创性的工作，但能够解决的例子很少，没有实现，而且这一领域仍然是出了名的技术性。根据我的专业知识和长期的准备工作，我将通过将不确定性算法与群体理论和几何方法联系起来，推动这一领域的理论和计算方面的发展。我的目标是更清晰地绘制景观的基本特征，不仅产生深刻的结果，而且还产生易于理解的文献和新的算法。一个重要的研究方向将是在最重要的无限群的类别中，如自由群、双曲群或某些幂零群和Artin群中，方程和非方程解以及可定义集的形式语言表征。我们的工作将给出具有复杂代数结构的集合的一种新的组合描述。2. 该项目的另一个目标是开发求解海森堡群和二面体Artin群方程的算法。目前还没有这样的算法存在，这些问题将需要突破性的、新颖的方法。3. 该项目最雄心勃勃的目标是利用Diekert， Elder和我提出的新的非确定性算法的核心信息，不仅提取形式语言特征，而且提取自由群中变体的代数结构，并将其与Makanin-Razborov图给出的信息进行比较。该项目最具创新性的方面是其真正的跨学科性质：我们将使用计算机科学和组合学的工具来回答植根于群论，非交换代数几何和逻辑的问题，反之亦然，我们将使用代数和几何结果来改进和推广现有的计算方法。

Solving equations has always been a central question for mathematics. Whether searching for the roots of a polynomial or solving a differential equation, finding or approximating the solutions is an essential part of science, from pure to applied, and understanding the properties of the solutions opens up worlds of algebraic, dynamical, geometric or logical structure. This project centres on finding and understanding the solutions of equations in infinite nonabelian discrete groups, a topic at the wild frontier between solvable and unsolvable, with far-reaching applications to algebra, logic, geometry and theoretical computer science. Understanding solutions is crucial in order to expand algebraic geometry to a non-commutative setting, to master the first order theory of a structure, to determine isomorphism between two hyperbolic groups, to advance unification theory, and to answer questions about combinatorics on words. Despite the groundbreaking work in the this area by Makanin, Razborov, Sela, Kharlampovich, Miasnikov and others, very few examples can be tackled, no implementation exists, and the area remains notoriously technical. On the strength of my expertise and long term preparatory work towards the objectives of this project, I will push forward both the theoretical and computational side of this area by linking nondeterministic algorithms to group theoretic and geometric approaches. I aim to map the essential features of the landscape more clearly and produce not only deep results, but also accessible literature and new algorithms.1. An important research direction will be the formal language characterisation of solutions of equations and inequations, as well as definable sets, in the most important classes of infinite groups, such as free, hyperbolic or certain nilpotent and Artin groups. Our work will give a new, combinatorial description of sets that have a complex algebraic structure. 2. Another goal of the project is to develop algorithms that solve equations in the Heisenberg group and dihedral Artin groups. At the moment no such algorithms exist, and these problems will require groundbreaking, novel approaches. 3. The most ambitious goal of the project is to exploit the information lying at the core of the new, nondeterministic algorithm due to Diekert, Elder and myself in order to extract not just formal language characterisations, but the algebraic structure of varieties in free groups, and compare this to the information given by Makanin-Razborov diagrams.The project's most innovative dimension is its authentic interdisciplinary nature: we will use tools from computer science and combinatorics to answer questions rooted in group theory, non-commutative algebraic geometry and logic, and vice versa, we will use algebraic and geometric results in order to improve and generalise the existing computational approaches.