34533255
Clifford Term Rewriting for Geometric Reasoning in 3D
Clifford algebra formalism has been used recently in combination with standard term-rewriting techniques for proving many non-trivial geometric theorems. The key issue in this approach consists in verifying whether two Clifford expressions are equal. This paper is concerned with the generalization of the work to 3D geometric problems. A rewriting system is proposed and its theoretical properties are investigated. Some examples and potential applications are also presented.
5752689
Stability analysis of biological systems with real solution classification
This paper presents a new and general approach for analyzing the stability of a large class of biological networks, modeled as autonomous systems of differential equations, using real solving and solution classification. The proposed approach, based on the classical technique of linearization from the qualitative theory of ordinary differential equations yet with exact symbolic computation, is applied to analyzing the local stability of the Cdc2-cyclin B/Wee1 system and the Mos/MEK/p42 MAPK cascade, two well-known models for cell and protein signaling that have been studied extensively in the literature. We provide rigorous proofs and generalizations for some of the previous results established experimentally and report our new findings.
10570969
Clifford Algebraic Calculus for Geometric Reasoning with Application to Computer Vision
In this paper we report on our recent study of Clifford algebra for geometric reasoning and its application to problems in computer vision. A general framework is presented for construction and representation of geometric objects with selected rewrite rules for simplification. It provides a mechanism suitable for devising methods and software tools for geometric reasoning and computation. The feasibility and efficiency of the approach are demonstrated by our preliminary experiments on automated theorem proving in plane Euclidean geometry. We also explain how non-commutative Grobner bases can be applied to geometric theorem proving. In addition to several well-known geometric theorems, two application examples from computer vision are given to illustrate the practical value of our approach.
35725775
A simple method for implicitizing rational curves and surfaces
Abstract This paper presents a simple method for converting rational parametric equations of curves and surfaces into implicit equations. The method proceeds via writing out the implicit polynomial F of estimated degree with indeterminate coefficients u i , substituting the rational expressions for the given parametric curve or surface into F to yield a rational expression g / h in the parameter s (or s and t ), equating the coefficients of g in terms of s (and t ) to 0 to generate a sparse, partially triangular system of linear equations in u i with constant coefficients, and finally solving the linear system for u i . If a nontrivial solution is found, then an implicit polynomial is obtained; otherwise, one repeats the same process, increasing the degree of F . Our experiments show that this simple method is efficient. It performs particularly well in the presence of base points and may detect the dependency of parameters incidentally.
24532367
Elimination procedures for mechanical theorem proving in geometry
In this paper, methods for the algebraic decision problem of mechanical theorem proving in elementary geometry are described on the basis of some elimination procedures for polynomial systems. The methods can determine whether or not a geometric theorem is generically true and whether it is true or false for each of the components including degenerate ones, with projection and irreducible decomposition. Theorems which have been proved using an implementation of the methods in Maple include the Simson Theorem, Butterfly Theorem, Secant Theorem, Feuerbach Theorem, Steiner Theorem, Steiner-Lehmus Theorem, Morely Theorem and Thébault-Taylor Theorem, of which some are taken as illustrative examples in the paper.
10779017
On Wu's Method for Proving Constructive Geometric Theorems
In 1977 Wu Wen-tsiin discovered an efficient method for mechanical theorem proving. This method has been applied to prove and discover theorems in various kinds of geometries. Based on an extension of one of Wu's algorithmic procedures, the author implemented a prover CPS for proving so-called constructive geometric theorems, as well as a general theorem prover PS. Using this prover we proved more than one hundred non-trivial theorems and discovered also a number of interesting ones. This paper is a summarization of our early work, as a abbreviation of the chapter 2 from my Chinese doctoral dissertation.
499811
Laser Needle Guide for the Sonic Flashlight
We have extended the real-time tomographic reflection display of the Sonic Flashlight to a laser guidance system that aims to improve safety and accuracy of needle insertion, especially for deep procedures. This guidance system is fundamentally different from others currently available. Two low-intensity lasers are mounted on opposite sides of a needle aimed parallel to the needle. The needle is placed against a notch in the Sonic Flashlight mirror such that the laser beams reflect off the mirror to create bright red spots on the flat panel display. Due to diffuse reflection from these spots, the virtual image created by the flat panel display contains the spots, identifying the projected destination of the needle at its actual location in the tissue. We have implemented our design and validated its performance, identifying several areas for potential improvement.
9827143
Making Predicate Abstraction Efficient: How to Eliminate Redundant Predicates
In this paper we consider techniques to identify and remove redundant predicates during predicate abstraction. We give three criteria for identifying redundancy. A predicate is redundant if any of the following three holds (i) the predicate is equivalent to a propositional function of other predicates. (ii) removing the predicate preserves safety properties satisfied by the abstract model (iii) removing it preserves bisimulation equivalence. We also show how to efficiently remove the redundant predicates once they are identified. Experimental results are included to demonstrate the effectiveness of our methods.
8658919
Using Combinatorial Optimization Methods for Quantification Scheduling
Model checking is the process of verifying whether a model of a concurrent system satisfies a specified temporal property. Symbolic algorithms based on Binary Decision Diagrams (BDDs) have significantly increased the size of the models that can be verified. The main problem in symbolic model checking is the image computation problem, i.e., efficiently computing the successors or predecessors of a set of states. This paper is an in-depth study of the image computation problem. We analyze and evaluate several newheuristics, metrics, and algorithms for this problem. The algorithms use combinatorial optimization techniques such as hill climbing, simulated annealing, and ordering by recursive partitioning to obtain better results than was previously the case. Theoretical analysis and systematic experimentation are used to evaluate the algorithms.
16321846
Semantics modeling based image retrieval system using neural networks
Semantics based image retrieval techniques show a promising direction to the development of CBIR systems. To design such systems, semantics modeling is one of the most difficult tasks. This paper aims to develop a semantics modeling approach using neural networks. In our work, a neural network is utilized to memorize the semantic patterns within the images. An intelligent image retrieval system is designed based on this model. User's relevance feedback is used for enhancing the retrieval performance. Experimental results from the prototype system demonstrate the effectiveness of the proposed approach.
2125782
On the bounded domination number of tournaments
Abstract In a simple digraph, a star of degree t is a union of t edges with a common tail. The k -domination number γ k (G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ k (T)=⌈n/(k+1)⌉ when T is a tournament with n⩾14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n -vertex tournament is dominated by at most lg n− lg lg n+2 vertices.