基于k阶秩函数的线性赋值循环程序的终止性分析

循环程序的终止性是确保循环程序完全正确的必要条件。 如果给定的线性赋值循环程序不存在传统定义的线性秩函数,那么基于传统定义的秩函数终止性证明方法将失效。基于Aⁿx的精确计算,对传统的秩函数概念进行了扩展,提出了k阶秩函数的概念。使用RegularChains软件包给出了合成k阶秩函数的具体方法。实验结果表明,相比于传统定义的线性秩函数,k阶秩函数的适应范围更广。对于 不能用传统定义的秩函数证明其终止性的部分循环程序,可以基于k阶秩函数来证明,从而体现了所提方法的优越性。     

多项式循环程序的秩函数探测

秩函数法是循环程序终止性分析的主流方法.针对一类多分支多项式循环程序,这类程序的秩函数计算问题被证明可归结为单形上正定多项式的探测问题,从而便于利用线性规划工具Simplex去计算这类程序的秩函数.不同于现有基于柱形代数分解的量词消去算法,该方法能够在可接受的时间内计算更为复杂的多项式秩函数.     

单分支线性约束循环程序的终止性分析

秩函数法是循环终止性分析的主要方法,秩函数的存在表明了循环程序是可终止的.针对单分支线性约束循环程序,提出一种方法对此类循环的终止性进行分析.基于增函数法向空间的计算,该方法将原程序空间上的秩函数计算问题归结为其子空间上的秩函数计算问题.实验结果表明,该方法能有效验证现有文献中大部分循环程序的终止性.     

基于Dixon结式和逐次差分代换的多项式秩函数探测方法

秩函数探测是循环程序终止性分析的重要方法，目前，已有很多研究者致力于为线性循环程序探测对应的线性秩函数，然而，针对具有多项式循环条件和多项式赋值的多项式型的循环，现有的秩函数探测方法还有所不足，解决方案大多是不完备的、或者具有较高的时间复杂度。针对现有工作对于多项式秩函数探测方法不足的问题，基于扩展Dixon结式（KSY方法）和逐次差分代换（SDS）方法，提出一种为多项式循环程序探测多项式型秩函数的方法。首先，将待探测的秩函数模板看作带参数系数的多项式，将秩函数的探测转换为寻找满足条件的参数系数的问题；然后，进一步将问题转换为判定相应的方程组是否有解的问题，至此，利用KSY方法中的扩展的Dixon结式，将问题更进一步简化为带参系数多项式（即结式）严格为正的判定问题；最后，利用SDS方法，找到一个充分条件，使得得到的结式严格为正，此时，可以获取满足条件的参数系数的取值，从而找到一个满足条件的秩函数，通过实验验证该秩函数探测方法的有效性。实验结果表明，利用该方法，可以有效地为多项式循环程序找到多项式秩函数，包括深度为d的多阶段多项式秩函数，与已有方法相比，该方法能够更高效地找到多项式秩函数，对于基于柱形代数分解（CAD）方法的探测方法因时间复杂度问题无法而应对的一些循环，利用所提方法能够在几秒内为这些循环找到秩函数。     

循环程序的界函数合成

作为循环程序终止性分析的主流方法,当前的秩函数方法大多局限于线性或多项式秩函数的求解.针对循环程序若不存在对应的线性或多项式秩函数,现有秩函数方法就无法证明其终止性的问题,提出一个新的方法来合成给定循环程序对应的界函数.对于给定的循环程序,倘若能找到其界函数,则表明该循环程序是可终止的.首先将界函数的求解问题转化为一个...     

基于深度学习和反例制导的循环程序秩函数生成

程序终止性判定是程序分析与验证领域中的一个研究热点. 针对非线性循环程序, 提出了一种基于反例制导的神经网络型秩函数的构造方法. 该方法采用学习组件和验证组件交互的迭代框架, 其中学习组件利用程序轨迹作为训练集合构造一个候选秩函数, 验证组件运用可满足性模理论(Satisfiability Modulo Theories, SMT)确保候选秩函数的有效性, 而由SMT返回的反例则进一步用于扩展学习组件中的训练集合以对候选秩函数进行精化.实验结果表明, 所提出的方法比已有的机器学习方法在秩函数的构造效率和构造能力上具有优势.     

改进型低秩线性回归新方法

对于遮挡、光照等影响因素,低秩线性回归模型具有很好的鲁棒性。LRRR(Low Rank Ridge Regression)以及DENLR(Discriminative Elastic-net Regularized Linear Regression)通过正则化系数矩阵在一定程度上减少了LRLR(Low Rank Linear Regression)产生的过拟合现象。但其没有考虑子空间数据的错误逼近,投影矩阵不能准确地将数据映射到目标空间。鉴于此,提出了一种运算更快、更具判别性的低秩线性回归分类新方法。首先,将0-1构成的矩阵作为线性回归的目标值;其次,利用核范数作为低秩约束的凸近似;然后,通过正则化各类别之间的距离矩阵和模型输出矩阵来降低过拟合,同时可以增强投影子空间的判别性;再次,利用增广拉格朗日乘子(Augmented Lagrangian Multiplier,ALM)优化目标函数;最后,在子空间中利用最近邻分类器进行分类。在AR、FERET人脸数据库、Stanford 40 Actions、Caltech-UCSD Bird以及Oxford 102 Flowers数据库上进行相关算法的对比实验,结果表明所提算法是有效的。     

基于SVM的多项式循环程序秩函数生成

程序终止性问题是自动程序验证领域中的一个研究热点.秩函数探测是进行终止性分析的主要方法.针对单重无条件分支的多项式循环程序,将其秩函数计算问题归结为二分类问题,从而可利用支持向量机（SVM）算法来计算程序的秩函数.与基于量词消去技术的秩函数计算方法不同,该方法能在可接受的时间范围内探测到更为复杂的秩函数.     

基于迭代轨迹划分的单分支循环程序终止性分析

秩函数作为循环程序终止性分析的重要方法已得到广泛研究。文中着重研究了单分支循环的终止性。首先提出了双向迭代循环概念,将单分支循环分为双向迭代循环和非双向迭代循环。其次,针对双向迭代循环程序,建立了一种划分思路,提出了三段式秩函数的概念,并证明了若该双向迭代循环存在三段式秩函数,则其是终止的。而对非双向迭代循环,引用增函数的划分思路,即利用增函数将原程序空间划分为更小的空间,并通过计算更小空间上的秩函数来证明原程序的终止性。最后,将三段式秩函数的计算问题归结为SVM分类问题,并利用工具Z3或bottema对由SVM所得的候选秩函数进行验证。     

Prolog程序中循环的终止性分析

本文对Prolog程序中的循环进行了分析,提出了一种识别无穷循环的简单直观方法,在此基础上给出了相应的避免或防止办法。     

关于正切换系统的共同线性copositive Lyapunov函数

研究了正线性系统的共同线性copositive Lyapunov函数。首先,基于几何性质给出了关于一对二阶正线性系统的定理的另一种证明。通过新的证明方法,把结果推广到有限个二阶正线性系统的情况.然后对三阶情况给出了一个结果。最后,对高阶的正线性系统给出了一些结果。     

一种密码函数存在性证明的新方法

密码函数在密码学中具有重要的研究价值.从组合的角度,给出了一种密码函数不存在性证明的新方法,并且得到了一些新结果,部分结果优于已有结论,这些结果可以部分证明不存在次数大于2的齐次旋转对称bent函数这一公开猜想.同时,利用多项式的最大公因子算法刻画了2次齐次旋转对称bent函数.该方法也可以用于刻画其他形式的bent函...     

分段线性函数应用于延时系统的最优控制

本文把分段线性函数引入到求解延时系统的最优控制中，推得延时线性系统二次型最优控制问题的分段控制解答及其状态轨线估计，算例结果表明，该算法比方块脉冲函数算法具有更高的计算精度。     

具有线性结构的弹性函数非线性度的新上界

讨论了具有线性结构的弹性函数的两个指标:沃什谱和非线性度,得到了具有线性结构的布尔函数的一些性质.利用沃尔什变换和汉明重量的方法,发现了:如果V是n元布尔函数,f(x)的线性结构,那么得到f(x)的沃尔什变换在为零这一事实,同时得到了一个布尔函数没有k(k≥0)维线性结构的充分条件.最后,利用以上结果推出了具有线性结构的弹性函数的非线性度的上界表达式.