The language complexity of problems in algebra and logic

代数和逻辑问题的语言复杂性

• 批准号: DP160100486
• 负责人: Prof Murray Elder
• 金额: $ 29.28万
• 依托单位: University of Technology Sydney
• 依托单位国家: 澳大利亚
• 项目类别: Discovery Projects
• 财政年份: 2016
• 资助国家: 澳大利亚
• 起止时间: 2016-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/DP160100486
• 关键词: language; complexity; problems; algebra; logic

This project focuses on a major problem at the intersection of algebra, logic and computer science, concerning equations over free groups and free monoids. Expected outcomes include a language-theoretic characterisation of solutions of equations in a wide class of groups and monoids, a language-theoretic understanding of the existential and first-order theories of free groups, and a classification of groups with indexed multiplication tables and EDT0L word problem. The project is designed to expand the frontiers of knowledge in theoretical computer science and pure mathematics, but in the longer term to deepen our understanding of computers, their computational power and intrinsic limitations.

这个项目的重点是在代数，逻辑和计算机科学的交叉点的一个主要问题，关于自由群和自由幺半群方程。预期的成果包括一个语言理论的特点方程的解决方案，在广泛的一类群体和monoid，语言理论的理解存在和一阶理论的自由群体，和分类的群体索引乘法表和EDT0L字的问题。该项目旨在扩大理论计算机科学和纯数学的知识前沿，但从长远来看，加深我们对计算机，其计算能力和内在局限性的理解。