美国留学

第35 ACM/IEEE计算机科学逻辑研讨会，http://lics.siglog.org/lics20/），称为LICS 2020，将于7月8日至7月11日在线举行（主要地点位于德国Saarbrcken，德国）。这次会议是理论计算机科学领域的顶级国际会议之一，像STOC和FOCS一样著名，并且在计算机科学领域享有很高的声誉。结果代表了理论计算机科学的最前沿，并且具有广泛而深远的学术影响力。

LIC对结果质量的要求非常高，很难收到论文。它每年仅收到全球50-60篇论文。自1986年首次在剑桥大学举行以来，总共有9篇论文并由中国的第一单元（包括2020年）签署并发表。今年，Xidian中只有一篇论文在中国被聘用，标题为“使街道的确定性紧缩”。这是迄今为止由LIC独立完成的第二篇论文，也是唯一由一个国内单位独立完成的论文。该论文是由田（Tian Cong）教授，博士生Wang Wensheng和Xi'an电子科学技术大学计算机科学技术学院Duan Zhenhua完成的。该论文最终完美地解决了非确定性街道自动机（简称NSA），Rabin Automata（DRA）的确定性问题，并获得了最佳的算法和渐近紧密绑定，以确定NSA至Parity Automata（DPA）。这是理论计算机科学领域的一项里程碑研究结果，是提高计算机软件和硬件系统信誉验证的时空效率的重要理论基础，也是逻辑系统（例如SNS，CTL*和计算）的判断过程的基础，并且也是解决Infinite Game Solving的关键。

关于无限单词自动机的复杂性的研究始于1960年代。 1988年，Safra提出了Safra树，并在1988年将其发表了，成为确定无限单词自动机的核心数据结构。关于街道自动机确定问题的研究始于1992年。在过去的28年中，从NSA到DRA的确定问题的州复杂性的上限和下限大约匹配；街道自动机的上限和下限之间仍然存在很大的差距。这次发表的论文通过引入新的节点命名规则提出了新的数据结构H-SAFRA树。节点的名称仅由索引标签确定，也就是说，一旦确定了节点的索引标签，该名称是唯一确定的，避免了节点命名对状态复杂性的影响，从而降低了NSA确定的复杂性。在此基础上，提出了LIR-H-SAFRA树，并通过引入LIR将NSA与DPTA的状态复杂性降低，以记录H-Safra树中的节点生成顺序。

Lir-H-Safra树插图

该论文进一步定义了完整的街道自动机以及与之匹配的L游戏。通过定义L游戏的不同作用，NSA到DRA的确切下限决定了状态的复杂性，这与文本中给出的算法复杂性（上边界）完全一致，从而终止了NSA对DRA的复杂性问题。同时，这项研究增加了NSA对DPA的状态复杂性的下限，并与本文中提出的算法复杂性（上边界）均匀匹配，从而*缩小了上边界和下边界之间的差距。

L游戏插图

本文的出版是国际学术界对学校在理论计算机科学领域的研究成就的认可以及学校对基础研究的长期支持的结果。据报道，田康教授和杜安·辛哈瓦教授长期以来一直坚持计算机科学领域的基础研究，并在理论计算机科学领域解决了许多重要问题。团队坚持将理论创新与结果的转变和实施相结合，并坚持领导创新和满足国家需求。基于理论研究，它提出了有效的软件和硬件系统验证技术，开发了软件可信度保证工具集MSV，包括20多个子工具以及FPGA设计和开发和验证软件XD-V2B，该软件已成功应用于Lunar Exporloration Project的第三阶段的主要国家项目。

（来源：Xidian新闻网络）