加速布尔匹配算法的研究

逻辑验证和综合中，布尔匹配利用有序二叉判定图（Ordered Binary Decision Diagram,OBDD)检验两个给定的逻辑函数是否相等。直接枚举每个函数中输入变量的各种排列顺序，并根据这些顺序进行匹配，算法时间复杂度为O(n!2^n2),n为变量数。为了提高匹配算法的效率，文中用最小项数目作为标签标定变量（变量组）。对比两函数 中变量（变量组）的标签，可删除不可能的排序，加快匹配过程。在此基础之上，利用重构将待匹配变量压缩在OBDD图的底部。利用这部分结构可以进一步区分变量。实验结果表明，该算法不仅变量区分能力要好于其他算法，且执行速度快，更具实用价值。     

对称检测算法的研究

对称是逻辑综合，逻辑优化以及映像技术领域中一个非常重要的性质，对于对称函数，可以使用特殊的逻辑综合程序来改进设计结果，使用对称也可以提高映像技术和等价检测的有效性，提出一种用于OBDD布尔函数对称性检测的精确有效的算法。     

基于动态描述逻辑的语义Web服务PE匹配算法

将基于描述逻辑断言构成的PE描述公理的有限集合看作一个本体知识库,因此有关PE的语义匹配问题就转化到两个基于描述逻辑的本体知识库之间的逻辑蕴含判定问题,然后将逻辑蕴含推理问题转化为本体库的可满足性检测问题,并通过可判的扩展算法解决,同时对匹配结果进行有意义的排序及分类.所提方法与现有方法相当的情况下,具有更高的查全率,能够更好地区分匹配结果.     

基于描述逻辑的概念检索模型

针对当前的概念检索模型存在没有语义特征的词典和缺乏知识库层面上的推理机制等问题,采用具有很强的表达能力和可判定推理功能的描述逻辑来实现概念的扩展检索.设计了一个基于描述逻辑的概念检索模型,并对其核心的推理算法作了进一步扩展,给出了相应算法的数学定义及其知识库的逻辑描述,并据此采用Jena和Racer推理引擎实现了一个基于描述逻辑的汽车导购的概念检索系统,可向用户提供有关汽车的分类、性能、报价等信息.实验结果表明:基于描述逻辑的概念检索模型实现了有效的隐含语义的检索,并通过关联概念联想实现了良好的用户启发和信息导航.     

采用OBDD实现快速子匹配提取

为提高模式匹配算法中子匹配提取过程的时间效率,采用有序二元决策图(ordered binary decision diagram,OBDD)与布尔函数相结合的方法,完成了与PCRE(perl compatible regular expressions)和谷歌的RE2库的对比实验研究。结果表明:基于OBDD的子匹配算法的性能比PCRE和RE2提高了约一到两个数量级。     

基于动态筛选算法的二元判定图的优化

作为逻辑布尔函数的一种高效简洁的描述方法,BDD规模结构对应着计算机实现算法的空间和时间复杂性。随着应用领域的不同,BDD的节点和路径的规模成为关注的两个焦点。文章讨论利用基于动态规划的筛选算法来实现从节点规模和路径的大小两方面对BDD的优化。在将筛选算法用于节点优化的基础上,从理论上提出了优化路径的思路及可行算法。     

逻辑正弦－余弦函数在数字电子技术中的应用

将正弦－余弦三角函数和布尔逻辑代数相结合，交叉形成逻辑正弦－余弦函数，其自变量像普通三角函数的自变量一样可以连续取值，而函数值象布尔逻辑函数一样只取逻辑值“０”和“１”，遵从逻辑代数的运算规则．逻辑正弦－余弦函数既具有正弦－余弦三角函数的某些性质，又具有布尔逻辑函数的特性，为分析、设计数字逻辑电路实现的信号处理系统，提供了一种数学工具和信号形式     

逻辑正弦—余弦函数在数字电子技术中的应用

将正弦－余弦三角函数和布尔逻辑代数相结合，交叉形成逻辑正弦－余弦函数，其自变量像普通三角函数的自变量一样可以连续取值，而函数值象布尔逻辑函数一样只取逻辑值“０”和“１”，遵从逻辑代数和运算规则，逻辑正弦－余弦函数既具有正弦－余弦三角函数的某些性质，又具有布尔逻辑函数的特性，为分析，设计数字逻辑电路实现的信号处理系统，提供了一种数学工具和信号形式。     

基于OBDD时序电路设计的验证

依据有序二叉判定图（OBDD）和计算树逻辑（或称分支时态逻辑）CTL（Computational Tree Logic)的基本原理，分析了基于OBDD和CTL的验证数据电路设计的基本原理，并在此基础上，给出了时序电路等价验证的方法。     

模拟退火算法在BDD变量最优排序中的应用

二叉判定图(BDD)作为表示布尔函数的有效工具,被广泛的应用到逻辑综合,布尔电路的测试等领域,但是在构造BDD的过程中变量的顺序对其结点数有很大的影响,本文将广泛应用于人工智能的模拟退火算法引入到BDD变量排序中,提出了一种寻找变量最优排序的新方法。该方法在寻求BDD最优变量排序的过程中,对处理器的处理时间和存储器的空间需求都有很大的改善。     

计算K-终端网络可靠度的一种新算法

讨论了由一个源点s到一个指定的点集K的网络可靠度问题。首先提出了两个网络门限变量化简原则及计算网络K-树和极小K-割的算法。然后,基于具有门限变量的布尔方程和有序二分决策图方法,给出网络K-终端可靠度算法。结果表明这种算法是有效的,改进并推广了Rauzy提出的算法。     

基于SAT和BDD的频繁序列挖掘技术

【目的】研究模式挖掘领域中的频繁序列挖掘技术,由于序列模式挖掘存在指数级的搜索空间,且传统的SAT求解算法无法高效求解大规模数据集的缺点,因此研究符号表示和操作技术,用来避免冗余计算。【方法】提出基于SAT的频繁序列挖掘的符号OBDD算法,基于深度优先算法的思想,首先将频繁序列挖掘问题构建为SAT模型,其次对变量进行排序并将约束子句分类后分别描述为OBDD,利用OBDD的"与"操作得到满足SAT的所有频繁序列模式。【结果】实例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,提高求解效率。     

拟代数簇包含关系的判定算法

判定拟代数簇的包含关系问题不能由计算其相应的饱和理想来确定 .利用一阶逻辑等价公式 ,将拟代数簇的包含关系问题化为检验另一个拟代数簇是否为空的问题 ,之后用 Grobner基方法加以判定 .文中给出了判定算法和计算实例     

基于关联规则和竞争凝聚算法的高压电缆缺陷识别模型

为便于运维人员及时准确判断高压电缆缺陷类型,提出了一种基于关联规则和竞争凝聚算法的高压电缆缺陷识别模型。该方法基于现有在线监测、离线试验和运维系统等数据,利用关联规则挖掘出不同缺陷类型与状态数据的关联关系,并建立电缆缺陷关联规则库;针对现有关联规则算法只能处理布尔型数据局限,采用竞争凝聚算法对连续型数据进行离散化处理;最后通过实例对所提的模型进行分析验证,仿真结果表明该模型识别准确率高、求解效率高、解释性好,有助于运维人员对电缆进行及时动态的维护管理。     

矿井通风网络最小割集不交和可靠度的计算

运用可靠性工程理论及不交型积之和定律,在大型网络系统可靠度计算的基础上,提出了矿井通风网络系统最大线性无关最小割集予以真子集涤除的不交和可靠度算法及其实现步骤.根据此算法,当最小割集按所含网络分支的多少进行升序排列时,还可进一步减少中间过程的计算量,从而达到最佳不交和简化计算的效果.实例分析表明:采用升序排列的最小割集并按不交型积之和定理予以真子集涤除的不交和处理后,不仅计算值等同于一般网络分析中用全概率公式计算的矿井通风网络系统可靠度,而且计算中具有所含网络分支布尔积的代数和项数少,计算工作量大为简化等特点.图2,表1,参9.     

基于频繁2-项集的数量关联规则挖掘方法研究

关联规则挖掘方法自提出以来已有很多改进算法,但均局限于布尔关联规则的挖掘.已有的数量关联规则挖掘主要考虑了连续属性值离散化、最优的数量关联规则挖掘等问题,但存在过小支持度和过小置信度问题.研究了这一问题并提出了一个在频繁2-项集的基础上挖掘数量关联规则的改进算法.它不仅可以用于典型的购物篮分析,还可以用于购物篮分析不能完成的关联规则挖掘问题,如带数量的捆绑销售问题.     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

代换定理的证明及其应用

本文给出了代换定理的优于文献[1]的证明方法,并把代换定理与其他定理结合,构造了一个判定DNF表达式永真性的算法,使代换定理得到实际应用。     

基于神经网络的模糊控制器及其应用

本文提出了一种基于神经网络的模糊控制器，采用神经网络技术实现模糊控制的知识规则的获取、隶属函数的确定及模糊推理。最后通过仿真实验证明了这种方法的有效性