基于H-等价的算法识别技术研究

蕴涵在程序代码中的语义是程序语言词法和语法的抽象表达,构成了人脑思维与机器思维交互过程的中间变换。从指称语义出发,结合具体语言,用形式化的方法讨论了语义等价和H-等价(Herbrand等价)。H-等价的判定条件相对来说更容易得到满足,具有更广泛的可用性。结合具体算法给出了H-等价在算法识别方面的应用成果及其局限性。

余树在图式流形拓扑分类中的应用

图式流形是以一个无向图G为框架产生出的管形曲面M(G)。本文讨论图式流形同胚分类的计数问题,该问题可转化为图的一类2-边着色问题,提出一种新的观点,探讨图式流形的等价分类,以便推进已有的工作。图的计数理论分为两大部分:标定图的计数与非标定图的计数。由于涉及同构判定,非标定图的计数较难。本文运用图论中的向量空间,包括圈空间及割空间,建立基本的计数方法,这一方面简化了群论方法的证明,另一方面更深入地揭示出同胚分类与圈结构的关系。以余树的概念为基础,提出"余树法",并得出结论:以余树的所有边导出子图为黑边子图,构成T-等价类的一个横贯;同时,以余树中所有不同构的边导出子图为黑边子图,构成H-等价类的一个代表系。