关于d-r.e度和n-r.e度的研究

本项目主要研究可计数性理论及其复杂性以及它们在计算机科学中的应用。特别是重点研究了d-r,e和n-r,e度的性质，研究工作按计划完成，并增加了数理逻辑在计算机科学中的应用课题。本项目的主要成果有（1）证明了Ms和Ns可以嵌入d-r,e度并保持O和L；（2）证明了Wtt-度中两区间无下确界的向上稠密性，（3）证明了可分枝的真d-r,e度的弱稠密性，（4）证明了S8可嵌入到d-r,e度中并保持O和1，（5）极小不可满足公式的性质。这些工作均为可计算性理论和复杂性理论中的前沿问题，受到了国际上同行的重视，并被多次引用，三年来共发表论文20篇，其中SCI杂志7篇，项目主持人丁德成应激在重要国际会议上作激请报告2次。