STR2: optimized simple tabular reduction for table constraints

Table constraints play an important role within constraint programming. Recently, many schemes or algorithms have been proposed to propagate table constraints and/or to compress their representation. In this paper, we describe an optimization of simple tabular reduction (STR), a technique proposed by J. Ullmann to dynamically maintain the tables of supports when generalized arc consistency (GAC) is enforced/maintained. STR2, the new refined GAC algorithm we propose, allows us to limit the number of operations related to validity checking and search of supports. Interestingly enough, this optimization makes simple tabular reduction potentially r times faster where r is the arity of the constraint(s). The results of an extensive experimentation that we have conducted with respect to random and structured instances indicate that STR2 is usually around twice as fast as the original STR, two or three times faster than the approach based on the hidden variable encoding, and can be up to one order of magnitude faster than previously state-of-the-art (generic) GAC algorithms on some series of instances. When comparing STR2 with the more recently developed algorithm based on multi-valued decision diagrams (MDDs), we show that both approaches are rather complementary.     

Strong local consistency algorithms for table constraints

Table constraints are important in constraint programming as they are present in many real problems from areas such as configuration and databases. As a result, numerous specialized algorithms that achieve generalized arc consistency (GAC) on table constraints have been proposed. Since these algorithms achieve GAC, they operate on one constraint at a time. In this paper we propose new filtering algorithms for positive table constraints that achieve stronger local consistency properties than GAC by exploiting intersections between constraints. The first algorithm, called maxRPWC+, is a domain filtering algorithm that is based on the local consistency maxRPWC and extends the GAC algorithm of Lecoutre and Szymanek (2006). The second algorithm extends the state-of-the-art STR-based algorithms to stronger relation filtering consistencies, i.e., consistencies that can remove tuples from constraints’ relations. Experimental results from benchmark problems demonstrate that the proposed algorithms are quite competitive with standard GAC algorithms like STR2 in some classes of problems with intersecting table constraints, being orders of magnitude faster in some cases.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

自适应表压缩方法优化STR算法

表约束,也称为外延式约束,是约束编程领域最常见的约束形式,表压缩方法通过紧凑的表示元组集可以极大地缩减空间消耗,同时加速 GAC 算法。笛卡尔乘积表示和短支持是表约束中最常见的两种表压缩方法,两种表压缩方法在同一问题上的压缩率是影响它们优化效果的主要原因。基于 STR 算法提出一种自适应表压缩方法,在求解问题时自适应选择压缩率大的表压缩方法,将自适应表压缩方法应用到 STR2 上提出了 STR2 Adaptive 算法,可以同时覆盖两种表压缩方法的优势。实验结果表明,STR2 Adaptive 算法在绝大部分实例上都能自适应选择最佳的表压缩方法,有效地减少了STR2算法空间消耗和CPU运行时间。然后将自适应表压缩方法扩展到采用了高效的比特向量表示的 STRbit 算法上提出了 STRbit Adaptive 算法。实验结果表明,STRbit Adaptive 算法效率同样普遍优于 STRbit 算法。     

一种基于时间戳的简单表缩减算法

表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容（generalized arc consistency,简称GAC）是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction（STR）是一类高效的维持GAC的算法.在回溯搜索中,STR动态地删除无效元组,降低了查找支持的开销,并拥有单位时间的回溯代价,在高元表约束上获得了广泛运用,并有大量基于STR的改进算法被提出,其中,元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想,为STR提出一种检测并删除无效元组和为变量更新支持的算法,作用于原始表约束并拥有单位时间的回溯代价.实验结果表明,该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.     

一种基于STR算法的新表压缩方法

约束传播是约束编程的关键方法,近些年来,一些约束传播算法中频繁用到简单表缩减(simple tabular reduction, STR)算法来降低约束表的空间消耗,同时提高广义弧相容(generalised arc consistent, GAC)算法的运行速度.短支持方法是在约束传播算法中使用最广泛的一种表压缩方式,但当约束表压缩率较低时,短支持方法提高运行速度效果不明显.因此提出一种压缩约束表的新算法STRO(simple tabular reduction optimization),结合短支持压缩和位操作,在提高STR算法的运行速度的同时压缩表空间效果更好.实验结果表明：在约束表的平均大小不是特别小的情况下,STRO与ShortSTR2,STR2算法相比,速度更快、效率更高;与STRbit算法相比,在时间上可以替代STRbit算法,但STRO算法的表压缩率更大、更加节省空间.     

Linear Time Algorithms for Exact Distance Transform

In 2003, Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) published a paper describing an algorithm that computes the exact distance transform in linear time (with respect to image size) for the rectangular binary images in the k-dimensional space ℝ ^k and distance measured with respect to L _p -metric for 1≤p≤∞, which includes Euclidean distance L ₂. In this paper we discuss this algorithm from theoretical and practical points of view. On the practical side, we concentrate on its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform, and experimentally compare implemented algorithms. We also describe the parallelization of these algorithms and discuss the computational time savings associated with them. All these implementations will be made available as a part of the CAVASS software system developed and maintained in our group (Grevera et al. in J. Digit. Imaging 20:101–118, 2007). On the theoretical side, we prove that our version of the signed distance transform algorithm, GBDT, returns the exact value of the distance from the geometrically defined object boundary. We provide a complete proof (which was not given of Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) that all these algorithms work correctly for L _p -metric with 1<p<∞. We also point out that the precise form of the algorithm from Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) is not well defined for L ₁ and L _∞ metrics. In addition, we show that the algorithm can be used to find, in linear time, the exact value of the diameter of an object, that is, the largest possible distance between any two of its elements.     

A global constraint for total weighted completion time for unary resources

We introduce a novel global constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the constraint, we propose an O(n ⁴) algorithm which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed global constraint significantly improves the performance of constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. We then apply the constraint to the multi-machine job shop scheduling problem with total weighted completion time. Our experiments show an order of magnitude reduction in search effort over the standard weighted-sum constraint and demonstrate that the way in which the job weights are associated with activities is important for performance.     

Transformational Derivation of an Improved Alias Analysis Algorithm

In this paper we use a program transformational approach to obtain an asymptotically improved may-alias analysis algorithm. We derive an O(N³) time algorithm for computing an intra-procedural flow sensitive may-alias analysis, where N denotes the number of edges in the program control flow graph (CFG). Our algorithm improves the previous O(N⁵) time algorithm by Hind et al. [19]. Our time complexity improvement comes without any deterioration in space complexity. We also show that for a large subclass of programs in which the in-degree and out-degree of all CFG nodes is bounded by a constant, our algorithm is linear in the sum of the number of edges in the CFG of the program and the size of the output, i.e., the size of the computed alias information, and is therefore asymptotically optimal. Our transformational algorithm derivation technique also leads to a simplified yet precise analysis of time complexity.The work in this paper was done when the author was a graduate student at New York University. This paper was originally submitted when the author was a Research Staff Member at the IBM T.J. Watson Research Center.     

基于时空约束和稀疏表示分类的目标跟踪算法

针对经典稀疏分类目标跟踪算法中目标模板和目标基的建模及更新方式效率低,跟踪性能不可靠等问题,提出一种新的目标跟踪算法,解释了时空约束原理,目标基、背景基、时序特征池的创建方法以及选择与抛弃两种基更新机制;该算法采用时序循环更新方式解决模板更新问题,结合稀疏表示分类和标准对冲实时计算目标坐标。相比其他几种经典目标跟踪算法,有效提高了在复杂背景下的目标跟踪性能。     

Geometry-based propagation of temporal constraints

In recent years, the Internet of Things (IoT) has been introduced to offer promising solutions in many areas. A big challenge faced by the IoT is to integrate heterogeneous information sources and process information effectively. As an important element in information integration, temporal reasoning is highly related to the dynamic, sequential aspect of both the information integration and the decision making process. Focusing on temporal reasoning, this paper introduces a method to represent both qualitative and quantitative temporal constraints in a 2-dimensional (2-D) space. Meanwhile, an efficient constraint-based geometric (CG) algorithm for propagating constraints (including inherent constraints and constraint pairs) on events in a 2-D space is proposed. A geometric recombination and intersection (GRI) method, a part of the CG algorithm, is presented to propagate one constraint pair from a geometric point. The experimental results show that in terms of both constructed and realistic benchmarks, the CG algorithm outperforms the existing Floyd-Warshall’s algorithm with the time complexity of O(n ³), especially for benchmarks with a large number of events.     

优化求解约束满足问题的MDDc和STR3算法

广义弧相容是求解约束满足问题应用最广泛的相容性,MDDc、STR2和STR3是表约束上维持广义弧相容应用较多的算法,其中MDDc基于对约束压缩表示的思想,将表约束表示成多元决策图,对各个元组之间存在较多交叠部分的约束具有很好的压缩效果;STR3同STR2一样基于动态维持有效元组的思想,当元组集规模缩减较慢时STR3维持广义弧相容的效率高于STR2.通过深入分析发现MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.本文分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR,对于同一操作,可以根据回溯搜索不同阶段的局势自适应地选择代价最小的实现方法,得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比原算法速度提升显著,其中AdaptiveSTR在一些问题上相比STR3提速三倍以上.     

State space approach to behavioral systems theory: the Dirac–Bergmann algorithm

This paper develops an approach to behavioral systems theory in which a state space representation of behaviors is utilised. This representation is a first order hybrid representation of behaviors called pencil representation. An algorithm well known after Dirac and Bergmann (DB) is shown to be central in obtaining a constraint free and observable (CFO) state space representation of a behavior. Results and criteria for asymptotic stability, controllability, inclusions and Markovianity of behaviors are derived in terms of the matrices of this representation which involve linear algebraic processes in their computation.     

Color to gray conversions in the context of stereo matching algorithms

This study tackles the image color to gray conversion problem. The aim was to understand the conversion qualities that can improve the accuracy of results when the grayscale conversion is applied as a pre-processing step in the context of vision algorithms, and in particular dense stereo matching. We evaluated many different state of the art color to grayscale conversion algorithms. We also propose an ad-hoc adaptation of the most theoretically promising algorithm, which we call Multi-Image Decolorize (MID). This algorithm comes from an in-depth analysis of the existing conversion solutions and consists of a multi-image extension of the algorithm by Grundland and Dodgson (The decolorize algorithm for contrast enhancing, color to grayscale conversion, Tech. Rep. UCAM-CL-TR-649, University of Cambridge, 2005) which is based on predominant component analysis. In addition, two variants of this algorithm have been proposed and analyzed: one with standard unsharp masking and another with a chromatic weighted unsharp masking technique (Nowak and Baraniuk in IEEE Trans Image Process 7(7):1068–1074, 1998) which enhances the local contrast as shown in the approach by Smith et al. (Comput Graph Forum 27(2), 2008). We tested the relative performances of this conversion with respect to many other solutions, using the StereoMatcher test suite (Scharstein and Szeliski in Int J Comput Vis 47(1–3):7–42, 2002) with a variety of different datasets and different dense stereo matching algorithms. The results show that the overall performance of the proposed MID conversion are good and the reported tests provided useful information and insights on how to design color to gray conversion to improve matching performance. We also show some interesting secondary results such as the role of standard unsharp masking vs. chromatic unsharp masking in improving correspondence matching.     

A Rigorous Global Filtering Algorithm for Quadratic Constraints*

This article introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robotics to chemistry. Classical filtering algorithms are based upon local consistencies and thus, are often unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraint systems. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global filtering algorithm that works on a tight linear relaxation of the quadratic constraints. The Simplex algorithm is then used to narrow the domains. Since most implementations of the Simplex work with floating point numbers and thus, are unsafe, we provide a procedure to generate safe linearizations. We also exploit a procedure provided by Neumaier and Shcherbina to get a safe objective value when calling the Simplex algorithm. With these two procedures, we prevent the Simplex algorithm from removing any solution while filtering linear constraint systems. Experimental results on classical benchmarks show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms.*This article is an extended version of [23].     

负表约束的简单表缩减广泛弧相容算法

广泛弧相容算法（generalized arc consistency,简称GAC）,是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势.     

On the computation of reference signal constraints for guaranteed tracking performance

This paper concerns the problem of determining constraints on reference signals for tracking systems such that the tracking performance can be guaranteed within a specified tolerance for any reference signal satisfying the constraints. We first consider the problem of computing derivative constraints, which are linear constraints on the (vector-valued) reference signal and its time derivatives, and present an off-line algorithm for computing inner approximations to supremal derivative constraint sets based on the hyperplane method for generating inner and outer approximations to the reachable set of states for the controlled system. No simulation is required. We then consider planning problems in which a finite number of parameters are selected to generate the reference signal. The derivative constraints are mapped into this parameter space. The simplicial approximation method is proposed as a method for computing an approximation to the set of admissible parameters. The resulting (linear) parameter constraints characterize a class of reference signals which can be successfully executed by the tracking system, thereby permitting supervisory planning and control to be carried out in the reference signal parameter space without simulating detailed models of the underlying system dynamics. We illustrate the computational algorithm and the application of derivative and parameter constraints for the problem of generating trajectories for a two-axis computer numerical control (CNC) cutting tool.     

求解约束可满足问题的eSTR算法优化

表约束方法是1种外延式知识表示方法,每个约束通过元组集直接枚举出其在1个变量集上允许或禁止的所有元组,直观易于理解,在约束程序中得到了深入的研究,这是因为表约束出现在如设计、数据库、配置以及偏好建模等许多现实世界的应用中.但随着约束的增多及其元组集增大,占有的空间与相容性检测效率成了关键问题.eSTR是1个将STR扩展到高阶相容的算法,通过深入分析eSTR算法后发现有2种优化方式:PW\\+{sup}数据结构和极小约束范围,同时证明了在极小约束范围上,约束网络仍然能够维持PWC+GAC,其中极小约束范围可以通过删除约束元组集中相应的列来降低eSTR2算法的空间消耗,而PW\\+{sup}数据结构能够通过避免不必要的PW支持检测来减少eSTR2的CPU运行时间,实验结果表明：2种优化方式和eSTR2相结合后能够同时减少算法的空间消耗和CPU运行时间,在许多类实例上明显优于eSTR2和eSTR2w.     

Simple linear string constraints

Modern web applications often suffer from command injection attacks. Even when equipped with sanitization code, many systems can be penetrated due to software bugs. It is desirable to automatically discover such vulnerabilities, given the bytecode of a web application. One approach would be symbolically executing the target system and constructing constraints for matching path conditions and attack patterns. Solving these constraints yields an attack signature, based on which, the attack process can be replayed. Constraint solving is the key to symbolic execution. For web applications, string constraints receive most of the attention because web applications are essentially text processing programs. We present simple linear string equation (SISE), a decidable fragment of the general string constraint system. SISE models a collection of regular replacement operations (such as the greedy, reluctant, declarative, and finite replacement), which are frequently used by text processing programs. Various automata techniques are proposed for simulating procedural semantics such as left-most matching. By composing atomic transducers of a SISE, we show that a recursive algorithm can be used to compute the solution pool, which contains the value range of each variable in concrete solutions. Then a concrete variable solution can be synthesized from a solution pool. To accelerate solver performance, a symbolic representation of finite state transducer is developed. This allows the constraint solver to support a 16-bit Unicode alphabet in practice. The algorithm is implemented in a Java constraint solver called SUSHI. We compare the applicability and performance of SUSHI with Kaluza, a bounded string solver.     

BRNGLR: a cubic Tomita-style GLR parsing algorithm

Tomita-style generalised LR (GLR) algorithms extend the standard LR algorithm to non-deterministic grammars by performing all possible choices of action. Cubic complexity is achieved if all rules are of length at most two. In this paper we shall show how to achieve cubic time bounds for all grammars by binarising the search performed whilst executing reduce actions in a GLR-style parser. We call the resulting algorithm Binary Right Nulled GLR (BRNGLR) parsing. The binarisation process generates run-time behaviour that is related to that shown by a parser which pre-processes its grammar or parse table into a binary form, but without the increase in table size and with a reduced run-time space overhead. BRNGLR parsers have worst-case cubic run time on all grammars, linear behaviour on LR(1) grammars and produce, in worst-case cubic time, a cubic size binary SPPF representation of all the derivations of a given sentence.