Knowledge representation for mathematical discovery: Three experiments in graph theory

This paper describes the nature of mathematical discovery (including concept definition and exploration, example generation, and theorem conjecture and proof), and considers how such an intelligent process can be simulated by a machine. Although the material is drawn primarily from graph theory, the results are immediately relevant to research in mathematical discovery and learning.The thought experiment, a protocol paradigm for the empirical study of mathematical discovery, highlights behavioral objectives for machine simulation. This thought experiment provides an insightful account of the discovery process, motivates a framework for describing mathematical knowledge in terms of object classes, and is a rich source of advice on the design of a system to perform discovery in graph theory. The evaluation criteria for a discovery system, it is argued, must include both a set of behavior to display (behavioral objectives) and a target set of facts to be discovered (factual knowledge).Cues from the thought experiment are used to formulate two hierarchies of representational languages for graphy theory. The first hierarchy is based on the superficial terminology and knowledge of the thought experiment. Generated by formal grammars with set-theoretic semantics, this eminently reasonable approach ultimately fails to meet the factual knowledge criteria. The second hierarchy uses declarative expressions, each of which has a semantic interpretation as a stylized, recursive algorithm that defines a class by generating it correctly and completely. A simple version of one such representation is validated by a successful, implemented system called Graph Theorist (GT) for mathematical research in graph theory. GT generates correct examples, defines and explores new graph theory properties, and conjectures and proves theorems.Several themes run through this paper. The first is the dual goals, behavioral objectives and factural knowledge to be discovered, and the multiplicity of their demands on a discovery system. The second theme is the central role of object classes to knowledge representation. The third is the increased power and flexibility of a constructive (generator) definition over the more traditional predicate (tester) definition. The final theme is the importance of examples and recursion in mathematical knowledge. The results provide important guidance for further research in the simulation of mathematical discovery.     

Evaluating part designs for automatic feeding in robotic assembly systems: A geometric analysis of the nesting of polyhedral objects

One of the problems encountered by automatic feeding devices, such as vibratory bowl feeders, in robotic assembly systems is nesting which leads to inseparability of parts and jamming. In this paper, we describe a design evaluation procedure to determine whether a part is prone to nesting and to quantify the degree of nesting. The proposed methodology reduces the 3-D protrusion-hole polyhedral containment problem of nesting to a 2-D polygon containment problem by employing a loop-based feature recognition scheme. Subsequently, the 3-D containment configuration is reconstructed from that of the 2-D by using a strategy calleddrop, pull and push. In this context, we introduce the notion of axis as a characteristic direction of a feature that facilitates the analysis of generalized 3-D polyhedral containment. The algorithms are applicable to generic B-Rep CAD data, and their time and space complexities are polynomial.     

Kernel Spectral Matched Filter for Hyperspectral Imagery

In this paper a kernel-based nonlinear spectral matched filter is introduced for target detection in hyperspectral imagery, which is implemented by using the ideas in kernel-based learning theory. A spectral matched filter is defined in a feature space of high dimensionality, which is implicitly generated by a nonlinear mapping associated with a kernel function. A kernel version of the matched filter is derived by expressing the spectral matched filter in terms of the vector dot products form and replacing each dot product with a kernel function using the so called kernel trick property of the Mercer kernels. The proposed kernel spectral matched filter is equivalent to a nonlinear matched filter in the original input space, which is capable of generating nonlinear decision boundaries. The kernel version of the linear spectral matched filter is implemented and simulation results on hyperspectral imagery show that the kernel spectral matched filter outperforms the conventional linear matched filter.     

线性八元树表示的三维客体群的连通分量标号和计数

本文提出二种算法分别标号和计数线性八元树表示的三维客体群的连通分量.这些操作典型地需要检查线性八元树中诸八分体在三个主方向上的面邻接对.根据这些邻接对,可以建造在计算机中用关联矩阵表示的邻接图.连通分量标号和计数是在关联矩阵上分别执行相应的操作而完成的.连通分量标号的执行时间是O(n+m·logm),而连通分量计数需要O(n)时间,其中m和n分别是线性八元树中八分体和邻接对的数目.     

Representing temporal knowledge in conceptual graphs

This study was motivated by some difficulties encountered by the authors when trying to express temporal knowledge using Sowa's conceptual graph (CG) approach. An overview of Sowa's approach is given and the difficulties encountered when trying to model temporal knowledge are outlined: the disparity of notations allowed by CG theory for expressing temporal information; the ambiguity and incompleteness of tense sspecification; the difficulty of harmonizing tenses and intergraph temporal relations. Various approaches suggested for representing time both in artificial intelligence and linguistics are presented, and an extension to Sowa's approach is proposed in which temporal and nontemporal knowledge are differentiated. In this model points in time are represented as well as time intervals. A semantic interpretation of verbs is provided based on an extension of Reichenbach's model of temporal markers. The authors show how their approach enables the representation of tenses as well as the aspectual properties of natural language sentences.     

Dynamic Waveband Switching in WDM Mesh Networks Based on a Generic Auxiliary Graph Model

Waveband switching (WBS) is a promising technique to reduce the switching and transmission costs in the optical domain of a wavelength-division multiplexing (WDM) network. This paper considers the problem of provisioning dynamic traffic using WBS in a WDM mesh network. The network of interest is a homogeneous WBS network, where each node has the functionality of WBS. The problem is called the dynamic WBS problem, which involves searching waveband-routes or wavelength-routes for the dynamically arriving traffic requests. The objective is to minimize the total switching and transmission costs in the optical domain. To solve the dynamic WBS problem, an auxiliary graph model capturing the network state is proposed. Based on the auxiliary graph, two heuristic on-line WBS algorithms with different waveband grouping policies are proposed, namely the wavelength-first WBS algorithm based on the auxiliary graph (WFAUG) and the waveband-first WBS algorithm based on the auxiliary graph (BFAUG). Simulation results indicate that WBS is an attractive technique which reduces the overall switching and transmission costs by up to 30% in the network. The results also show that the WFAUG algorithm outperforms the BFAUG algorithm in terms of port savings and cost savings.     

逻辑程序的一种并行执行模型

本文基于静态相关性分析和动态调整相结合的方法，提出了一种逻辑程序的执行模型，它不仅开发了“与“并行，同进也开发了一定的“或“并行，从而有效地加速了逻辑程序的执行。     

GIS中矢量图形的结构分析与VC++中的实现

简要讨论了GIS各类矢量图形元素间的空间拓朴结构及基位置关系 ,并用VC 6 . 0及MFC具体分析了圆弧与多边形区域的相交关系及实现。为利用VC开发专用图形软件提供了有用帮助。     

Node-pair reliability of network systems with small distances between adjacent nodes

A new method for computing the node-pair reliability of network systems modeled by random graphs with nodes arranged in sequence is presented. It is based on a recursive algorithm using the “sliding window” technique, the window being composed of several consecutive nodes. In a single step, the connectivity probabilities for all nodes included in the window are found. Subsequently, the window is moved one node forward. This process is repeated until, in the last step, the window reaches the terminal node. The connectivity probabilities found at that point are used to compute the node-pair reliability of the network system considered. The algorithm is designed especially for graphs with small distances between adjacent nodes, where the distance between two nodes is defined as the absolute value of the difference between the nodes’ numbers. The maximal distance between any two adjacent nodes is denoted by Γ(G), where G symbolizes a random graph. If Γ(G)=2 then the method can be applied for directed as well as undirected graphs whose nodes and edges are subject to failure. This is important in view of the fact that many algorithms computing network reliability are designed for graphs with failure-prone edges and reliable nodes. If Γ(G)=3 then the method's applicability is limited to undirected graphs with reliable nodes. The main asset of the presented algorithms is their low numerical complexity—O(n), where n denotes the number of nodes.