Topics in Space Bounded Computation

空间有限计算主题

• 批准号: 9009318
• 负责人: Balasubramania Kalyanasundaram
• 金额: $ 3.15万
• 依托单位: University of Pittsburgh
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-08-01 至 1993-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9009318&HistoricalAwards=false
• 关键词: Topics; Space; Bounded; Computation

The goal of this research is to study space bounded computations. Even though space bounded computations are somewhat less difficult to analyze than time bounded computations, little is known regarding the power of nondeterminism. This research attempts to understand underlying combinatorics in space bounded computations by looking at various restricted models of computation. The DSPACEılog n! =? NSPACEılog n! problem is approached by considering different models such as sublog space bounded machines, universal traversal sequence and multihead two way finite state automaton. These restricted models of computation raise interesting questions with direct consequence to DSPACEılog n! =? NSPACEılog n! problem. This research concentrates on developing and using tools like communication complexity to show lower bounds on space requirement in these models with the hope of understanding the space bounded computations.

本研究的目标是研究空间有界计算。 即使空间有限的计算在某种程度上不那么困难， 分析比时间有界的计算，鲜为人知的是， 非决定论的力量 这项研究试图了解 在空间有界计算的基础组合学， 各种受限的计算模型。 DSPACE日志n！=? NSPACEılog n！通过考虑不同的模型来处理问题 例如子对数空间有界机器、通用遍历序列 和多头双向有限状态自动机。 这些受限模型 提出了一些有趣的问题，其直接后果是 DSPACE日志！=? NSPACEılog n！问题. 本研究集中于 开发和使用沟通复杂性等工具， 在这些模型中的空间要求的界限，希望 理解有界空间计算。