Linear Quantifier Elimination

This paper presents verified quantifier elimination procedures for dense linear orders (two of them novel), for real and for integer linear arithmetic. All procedures are defined and verified in the theorem prover Isabelle/HOL, are executable and can be applied to HOL formulae themselves (by reflection). The formalization of the different theories is highly modular.     

Quantifier Elimination and Provers Integration

We exploit quantifier elimination in the global design of combined decision and semi-decision procedures for theories over non-disjoint signatures, thus providing in particular extensions of Nelson-Oppen results.     

Reduction and Quantifier Elimination Techniques for Program Validation

We study the automatic verification of programs with infinite or parameterized state space. This paper presents methods allowing the transformation of some second-order formulas expressing Hoare triples into equivalent formulas expressed in a weaker but decidable logic. Two techniques are considered: quantifier elimination and reduction to a finite domain. We illustrate these techniques on the validation of memory coherency protocols expressed in Unity.     

Simulation and Optimization by Quantifier Elimination

We present a highly optimized method for the elimination of linear variables from a Boolean combination of polynomial equations and inequalities. In contrast to the basic method described earlier, the practical applicability of the present method goes far beyond academic examples. The optimization is achieved by various strategies to prune superfluous branches in the elimination tree constructed by the method.The main application concerns the simulation of large technical networks of (electric, mechanical or hydraulic) components, whose characteristic curves are piecewise linear (or quadratic) in the variables to be eliminated. Typical goals are the computation of admissible ranges for certain variables and the detection of a malfunction of a network component. The algorithms are currently used in a commercial software system for industrial applications.Moreover, we extend the author's elimination method for parametric linear programming to the non-convex case by allowing arbitraryand–orcombinations of parametric linear inequalities as constraints. We present a new strategy for finding smaller elimination sets and thus smaller elimination trees for parametric linear programming. Some benchmark examples from thenetliblibrary oflpproblems show the significance of this strategy even for convex linear programming problems.     

Applying Quantifier Elimination to the Birkhoff Interpolation Problem

This paper is devoted to show how to use Computer Algebra and Quantifier Elimination to solve some particular instances of the Birkhoff Interpolation Problem. In particular, this problem is completely solved for degrees less than or equal to 3 and any number of nodes and several instances of degree 4 and 5 by computing all the incidence normal poised matrices with such characteristics. The used Computer Algebra and Quantifier Elimination includes manipulation of multivariate polynomials, computation of determinants of matrices with polynomial entries and the formal manipulation of univariate polynomial inequalities by using Sturm—Habicht sequences and the Sign Determination Scheme.     

基于净化网页的改进消重算法

互联网的迅猛发展导致网络中的网页呈指数级别爆炸式增长。为解决在海量网页中寻找信息的问题,搜索引擎成为了人们使用互联网的重要工具。提出了一种基于净化网页的改进消重算法,并将它与传统的消重算法进行了比较。该算法结合关键字搜索和签名（计算指纹）搜索各自的优势来完成网页搜索消重。实验结果证明该方法对网页消重效果很好,提高了网页消重的查全率和查准率。     

带n-元存在量词的描述逻辑MSC推理

分析了描述逻辑非标准推理的重要性,特别分析了描述逻辑MSC(Most Specific Concept)推理的研究现状和存在的问题.针对目前描述逻辑MSC推理不能处理n-元存在量词的不足,研究了带n-元存在量词的描述逻辑εL(n)的MSC推理问题.提出了一种新的εL(n)一描述图,利用描述树和描述图给出了描述逻辑εL(n)的MSC近似推理算法,并利用εL(n)-描述树嵌套和εL(n)-描述树描述图同态证明了MSC近似推理算法的正确性.作为一个附带的结果,利用εL(n)-描述树描述图同态给出了εL(n)-的实例推理算法,也证明了实例推理算法的正确性.     

碰撞问题中的量词消去算法的并行化研究

机器人技术中的碰撞问题可以被表示成量词消去问题，但由于有些碰撞问题的复杂性使得这些问题在单个微机上求解需要花费的时间很长或者根本就解不出来。本文提出了基于分布Maple系统下量词消去算法的并行化．并针对分布Maple系统的特点以及算法的特点，通过实例分析，给出了两种并行策略，以达到在Maple软件环境下提高处理器利用率，提高量词消去算法的效率的目的。     

改进YOLOv5的交通标志检测算法

交通标志检测在自动驾驶、辅助驾驶等领域是一个重要的环节,关乎到行车安全问题。针对交通标志中存在目标小、背景复杂等难点,提出一种基于改进YOLOv5的算法。提出区域上下文模块,利用多种扩张率的空洞卷积来获取不同感受野,进而获取到目标及其相邻区域的特征信息,相邻区域的信息对交通标志小目标检测起到重要补充作用,可以有效解决目标小的问题;在主干部分引入特征增强模块,进一步提高主干的特征提取能力,利用注意力机制与原C3模块结合,使网络更能聚焦小目标信息,避免复杂背景的干扰;在多尺度检测部分,将浅层特征层与深层检测层进行特征融合,可以同时兼顾浅层位置信息与深层语义信息,增加目标定位与边界回归的准确度,更有利于小目标检测。实验结果表明,改进后的算法在交通标志检测数据集TT100K上取得了87.2%的小目标检测精度、92.4%的小目标召回率以及91.8%的mAP,与原YOLOv5算法相比较,分别提升了3.5、4.1、2.6个百分点,检测速度83.3 frame/s;在CCTSDB数据集上mAP为98.0%,提升了2.0个百分点,检测速度90.9 frame/s。因此,提出的改进YOLOv5算法可以有效...     

Block Local Elimination Algorithms for Sparse Discrete Optimization Problems

Block local elimination algorithms for solving sparse discrete optimization problems are considered. A numerical example is provided. The benchmarking is done in order to determine the real computational capabilities of block elimination algorithms combined with SYMPHONY solver. The analysis of the results shows that for a sufficiently large number of blocks and rather small size of separators between the blocks for a staircase integer linear programming problem, local elimination algorithms in combination with the solver for subproblems in blocks allow a much faster solution of such problems than the solver itself used to solve the whole problem. The capabilities of the postoptimal analysis (warm start) are also considered for solving packages of integer linear programming problems for the corresponding blocks.     

改进YOLOv7的交通标志检测算法

自动驾驶技术的快速发展,导致对交通标志检测技术的要求日益提高.为解决YOLOv7算法在识别小目标时误检、漏检等问题,本文提出一种基于注意力机制的交通标志检测模型YOLOv7-PC.首先通过K-means++聚类算法对交通标志数据集进行聚类,获得适用于检测交通标志的锚框;其次在YOLOv7主干特征提取网络中引入坐标注意力机制,将交通标志的横向和纵向信息嵌入到通道中,使生成的特征信息具有交通标志的坐标信息,加强有效特征的提取;最后在加强特征提取网络中引入空洞空间金字塔池化,捕获交通标志多尺度上下文信息,在保证交通标志小目标分辨率的同时,进一步扩大卷积的感受野.在中国交通标志检测数据集(CCTSDB)上的实验表明,本文算法增强了识别小目标的能力,相较于YOLOv7模型,本文算法的m AP、召回率平均分别提高了5.22%、9.01%,是一种有效的交通标志检测算法.     

加权3D-Matching的改进算法

Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权3D-matching augmentation问题进行求解,即从一个最大加权的k-matching着手构造权值最大的(k+1)-matching.从问题的特殊结构特性出发,给出了加权3D-matching augmentation问题特有的性质: k- matching中存在2列使得该2列至少有2k/3元素被包含在(k+1)-matching中所对应的2列中.基于给出的性质,通过运用color-coding和动态规划技术,给出了一个时间复杂度为O* (4.823k)的参数算法,最终求解加权3D-matching问题.该算法较目前文献中的最好结果O* (5.473k)有了极大的改进.