Determining the number of internal stability of a graph

The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective.     

Function simulation,graph grammars and colourings

We prove that to any partial function ? defined on a finite set, there corresponds an infinite class of graphs that could be generated by a graph grammar such that each graph in the class represents the function in the sense that evaluation of the function at any point x of its domain can be simulated by finding the unique extension of a partial vertex colouring of the graph specified by x. We show that in the proposed setup, generating such simulator graphs as well as finding the colouring extensions can be computed effectively in polynomial time. We also discuss some applications of this scenario in producing instances of the graph colouring problem near its phase transition that can be applied in a cryptographic setting.     

Updating method for the computation of orbits in parallel and sequential dynamical systems

In this article, we provide a matrix method in order to compute orbits of parallel and sequential dynamical systems on Boolean functions. In this sense, we develop algorithms for systems defined over directed (and undirected) graphs when the evolution operator is a general minterm or maxterm and, likewise, when it is constituted by independent local Boolean functions, so providing a new tool for the study of orbits of these dynamical systems.     

Constraint graph-based frequent pattern updating from temporal databases

There have been many kinds of association rule mining (ARM) algorithms, e.g., Apriori and FP-tree, to discover meaningful frequent patterns from a large dataset. Particularly, it is more difficult for such ARM algorithms to be applied for temporal databases which are continuously changing over time. Such algorithms are generally based on repeating time-consuming tasks, e.g., scanning databases. To deal with this problem, in this paper, we propose a constraint graph-based method for maintaining frequent patterns (FP) discovered from the temporal databases. Particularly, the constraint graph, which is represented as a set of constraint between two items, can be established by temporal persistency of the patterns. It means that some patterns can be used to build the constraint graph, when the patterns have been shown in a set of the FP. Two types of constraints can be generated by users and adaptation. Based on our scheme, we find that a large number of dataset has been efficiently reduced during mining process and the gathering information while updating.     

Note on winning positions on pushdown games with ω-regular conditions

We consider infinite two-player games on pushdown graphs. For parity winning conditions, we show that the set of winning positions of each player is regular and we give an effective construction of an alternating automaton recognizing it. This provides a DEXPTIME procedure to decide whether a position is winning for a given player. Finally, using the same methods, we show, for any ω-regular winning condition, that the set of winning positions for a given player is regular and effective.     

A database system of mechanical components based on geometric and topological similarity. Part I: representation

A database of mechanical components is an important issue for some manufacturing activities such as cost estimation, process planning, and design by case-based reasoning. In this paper, we give the representation scheme of the CAD model in such a database. Components are represented using attributed graphs in which the nodes correspond to the surfaces of the component and the links correspond to the edges of the component. The graph is based on the standard for the exchange of product information (STEP) physical file of the component. STEP file should be unique for a single component regardless of the underlying CAD system. The process of creating the graph of a component constitutes two sub-tasks: (i) importing the CAD model from the CAD system in STEP format and (ii) transforming the STEP data into attributed graph-based representation. The graph and its attributes describe the topology of the component completely together with some geometric data that are not dependent on any coordinate system such as surface type and curve type. These geometric data are helpful in the retrieval and matching processes in the database.     

基于本体集成的资源共享平台

资源共享是许多数据整合项目需要完成的首要任务。本体作为知识共享的有力工具，近来被广泛应用于数据整合项目中。针对共享的资源已存在各自对应本体的情况，提出了一个基于本体集成的资源共享平台实现方法。重点讨论了本体集成过程中不一致性的检查、处理问题和概念层次统一的问题，并以实际项目为例，介绍了所研究的方法如何运用于实际项目中。     

Completeness of the Accumulation Calculus

The accumulation calculs(AC for short)is an interval based temporal logic to specify and reason about hybrid real-time systems.This paper presents a formal proof system for AC,and proves that the system is complete relative to that of Interval Temporal Logic(ITL for short)on real domain.