Topics in Algorithms and Complexity

算法和复杂性主题

• 批准号: 8805978
• 负责人: Martin Furer
• 金额: $ 14.1万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-09-01 至 1991-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8805978&HistoricalAwards=false
• 关键词: Topics; Algorithms; Complexity

This research concerns main areas of algorithms and complexity. In graph isomorphism testing, a search for unifying sequential and parallel algorithms solving efficiently several of the known tractable cases, in particular the classes of graphs with bounded valence or eigenvalue multiplicity, will be unitiated. In communication complexity, specific problems in the deterministic and probabilistic models will be investigated. Besides the standard application of communication complexity to the AT2 complexity in VLSI, this project will also consider applications to lower bound problems. In learnabiliy theory, the kearning of language classes for a variety of learning protocols will be investigated. Possible extensions and their limitations of algorithms for learning finite automata, Marcov chains, as well as deteministic one counter automata will be considered.

本研究涉及算法和复杂性的主要领域。在 图同构测试，寻求统一的顺序和 并行算法有效地解决了几个已知的易处理的 的情况下，特别是类图有界价或 特征值多重性，将被统一。 连通 复杂性，确定性和概率性中的特定问题 将对模型进行研究。 除了标准的应用之外， 通信的复杂性AT2的复杂性在VLSI中，该项目 也将考虑应用于下限问题。在学习上 理论，语言课的知识，各种学习 协议将被调查。 可能的扩展及其 学习有限自动机，马尔可夫链， 以及确定性的一个计数器自动机将被考虑。