Mathematical Sciences: Group Theory and Formal Language Theory

数学科学：群论和形式语言理论

• 批准号: 8908887
• 负责人: Paul Schupp
• 金额: $ 4.3万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-06-15 至 1992-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8908887&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Group; Theory; Formal

This research is concerned with the connections between combinatorial group theory and the theory of automata and formal languages. The principal investigator will show that many combinatorial properties of groups, such as having an automatic structure or a rational growth function, can be characterized in terms of the corresponding Cayley group possessing a regular spanning tree with certain additional properties. Formal language theory is the theory of subsets of free monoids which are determined by certain kinds of machines. This research is concerned with the interactions of formal language theory and group theory. This work is important both in group theory and in theoretical computer science.

这项研究关注的是 组合群论和自动机理论， 形式语言首席研究员会证明 群的许多组合性质，例如具有 自动结构或合理的增长函数，可以是 用相应的Cayley群来刻画 拥有一个规则的生成树， 特性. 形式语言理论是自由语言子集理论 由某种机器确定的幺半群。这 研究关注的是形式语言的相互作用 理论和群论。这项工作是重要的， 理论和理论计算机科学。