Geometric constraint solving with geometric transformation

This paper proposes two algorithms for solving geometric constraint systems. The first algorithm is for constrained systems without loops and has linear complexity. The second algorithm can solve constraint systems with loops. The latter algorithm is of quadratic complexity and is complete for constraint problems about simple polygons. The key to it is to combine the idea of graph based methods for geometric constraint solving and geometric transformations coming from rule-based methods.

Solving geometric constraints with genetic simulated annealing algorithm

This paper applies genetic simulated annealing algorithm (SAGA) to solving geometric constraint problems. This method makes full use of the advantages of SAGA and can handle under-/over- constraint problems naturally. It has advantages (due to its not being sensitive to the initial values) over the Newton-Raphson method, and its yielding of multiple solutions, is an advantage over other optimal methods for multi-solution constraint system. Our experiments have proved the robustness and efficiency of this method.

A Constructive Approach to Solving Geometric Constraint Systems

This paper proposes a constructive approach to solving geometric constraint systems.The approach incorporates graph-based and rule-based approaches, and achieves interactive speed.The paper presents a graph representation of geometric conStraint syStems, and discusses in detailthe algorithm of geometric reasoning based on poinl-cluster reduction. An example is made forillustration.

Defeating constraint based program analysis with temporal correlation function

Constraint based program analysis is widely used in program validation, program vulnerability analysis, etc. This paper proposes a temporal correlation function to protect programs from analysis. The temporal correlation function can be applied to resist against both static and dynamic function summary and eoncolie testing. What＇ s more, the temporal correlation function can produce different outputs even with same input. This feature can be used to damage the premise of function summary as well as prevent concolie testing process to run the new branch with new input. Experiment results show that this method can reduce efficiency and path coverage of concolic testing, while greatly in- creasing the difficulty of constraint based program analysis.

Research on an algorithm for solving parameter ranges in parametric drawing systems

To solve the problem that in parametric drawing systems, unreasonable parameter values in a parametric model often result in an improper shape of a geometric object, this paper proposes a novel algebraic algorithm for determining the valid range of parameter values in certain 2-dimensional parametric drawing systems. This algorithm can solve valid range of parameters such as radius and coordinate of centre points of parametric models with only linear segments and circles. The result of the study shows that all values within the valid range provided by this algorithm can ensure that the topological shape of a geometric object does not change after reconstruction, and to some extent, this algorithm can significantly promote the efficiency of parametric drawing system design and the intel- lectual level of human-computer interaction. The analysis shows that complexity of this algorithm is O（n2）.

Automated String Constraints Solving for Programs Containing String Manipulation Functions

The ability to solve various constraints is a principal factor of automatic constraint solvers. Most object-oriented languages treat a character string as a primitive data type which is manipulated by string library functions. Most constraint solvers have limitations on their input constraints, such as strong restrictions on the expressiveness of constraints or lack of the ability to solve hybrid constraints. These limitations hinder applying automated constraint solvers on program analysis techniques for programs containing strings and string manipulation functions. We propose an approach to automatically solve program constraints involving strings and string manipulation functions. Based on the character array model, we design a constraint language which contains primitive operations to precisely describe the constraints of commonly used string manipulation functions. The translated string constraints together with numeric constraints are then solved by a two- phase test generation procedure： firstly, a partial solution is obtained to satisfy the arithmetic constraints of the position variables, and the solution is utilized to simplify the string constraints into pure character array constraints; secondly, the pure array constraints are solved by an off-the-shelf array-specific theory based constraint solver. We integrate the approach into an automated testing tool to support the generation of string test cases, and then perform experiments. The results of the experiments prove that the integration of the proposed approach promotes the testing coverage of the existing testing tool, and the integrated tool has an advantage of handling specific string manipulation functions compared with an existing string solver.

A Survey of the Rule Language RL/1

In this paper we introduced the RL project which aims to integrate logic progrmming,relational databases and constraint solving in a single relational framework.We gave a summary of the architecture of the RL/1 system and shortly discussed the characteristics of the RL/1 language.A target of the project has become to turn the RL/1 system into an industrial strength database interface.