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.     

David W. Johnson: Award for Distinguished Contributions of Applications of Psychology to Education and Training.

Provides the biography of David W. Johnson and announces that he has won the Award for Distinguished Contributions of Applications of Psychology to Education and Training for programmatic research, comprehensive research reviews, and revision of theory over four decades of persistence that have provided the knowledge foundation for cooperative learning, constructive controversy, conflict resolution, and peer mediation training. A selected bibliography is also provided. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

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

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

Alleviating convergence problems in Group Support Systems

Not all Group Support Systems are identical, as is demonstrated by their software implementations. We discuss two existing implementations of group support tools and the process models underlying them. We demonstrate that fundamental to both processes is the merging or integration of individual data. Based on this and other empirical research, the Shared Context Model (SCM) of cooperative work is adopted and we show that it supports existing processes and others. We expect that groups will find merging their work easier with the SCM. This model is presented and embedded in the architecture and implementation of four group tools. Because these tools are destined to be used by dispersed groups, synchronously or asynchronously, an object-based communication and control mechanism is incorporated. Finally, as graphics and multi-tasking have been shown to be increasingly important, the tools are implemented in Microsoft Windows for personal computers attached to local area networks.     

不完全信息下的最终报价仲裁

基于争议双地仲裁人的裁决值有不同的概率估计，而这些估计是双方共同知识这一前提分析最终报价中仲裁，把它构造成一个不完全信息的非零和对策模型。然后给出了局部、全局Ｎａｓｈ平衡报价策略存在唯一的充分条件，最后探讨了双方认识存在的差异对争议人报价行为的影响。     

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

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