12973064
Integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems
This paper presents some results of integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems. The intention of this research is to use predicate transition nets as a specification method and to use first order temporal logic as a verification method so that their strengths — the easy comprehension of predicate transition nets and the reasoning power of first order temporal logic can be combined. In this paper, a theoretical relationship between the computation models of these two formalisms is presented; an algorithm for systematically translating a predicate transition net into a corresponding temporal logic system is outlined; and a special temporal refutation proof technique is proposed and illustrated in verifying various concurrent properties of the predicate transition net specification of the five dining philosophers problem.
19528385
A semi-formal approach to assist software design with reuse
Design with reuse has been accepted as a cost-effective way to software development. Software reuse covers the process of identification, representation, retrieval, adaptation, and integration of reusable software components. In this paper, we propose a semi-formal approach to software reuse. The approach consists of the following major steps: (1) software components are annotated with formal information, (2) the software components are then translated into predicate transition nets, and (3) consistency checking of the reusable and new components is carried out using the reachability analysis technique of predicate transition (PrT) nets. The approach is demonstrated through an example.
28749706
An Improved Algorithm for Concurrency Control in Distributed Database Systems
Abstract Deadlock and livelock prevention is critical in concurrency control of distributed database systems. This paper presents an improved algorithm for concurrency control, which not only prevents deadlock and livelock problems but also improves system efficiency by lowering restart ratio and communication cost. The proposed algorithm is effective in environments where most transactions have one-way request (either forward waiting or backward waiting).
46303239
Object Orientation in Hierarchical Predicate Transition Nets
In this paper, an approach of using hierarchical predicate transition nets (HPrTNs in the sequel) for object-oriented specification is proposed. The realization of various object-oriented features (including encapsulation, inheritance, and polymorphism) in HPrTNs is presented and is demonstrated with examples. We believe that the approach can achieve the benefits of the object-oriented methods while maintaining the analyzability of HPrTNs.
20452185
A methodology for test selection
Software creation requires not only testing during the development cycle by the development staff, but also independent testing following the completion of the implementation. However in the latter case, the amount of testing that can be carried out is often limited by time and resources. At the very most, independent testing can be expected to provide 100% test coverage of the test requirements (or specifications) associated with the software element with the minimum of effort. This paper describes a methodology employing integer programming by which the amount of testing required to provide the maximum possible test coverage of the test requirements (for the given test set) is assured while at the same time minimizing the total number of tests to be included in a test suite. A collateral procedure provides recommendations on which tests might be eliminated if less than 100% test coverage of the test requirements is permitted. This latter procedure will be useful in determining the risk of not running the minimum set of tests for 100% test coverage. A third process selects from the test matrix the set of tests to be applied to the system following maintenance modification of any test requirements-- that is, to provide a submatrix for regression testing. The potential benefits for applying the integer programming technique in test data selection is also discussed.
14218377
A Methodology for Constructing Predicate Transition Net Specifications
In this paper, a methodology for constructing hierarchical and structured predicate transition net specifications is developed, which includes new systematic notation extensions for supporting various transformation techniques upon predicate transition nets and several rules for applying such transformation techniques. The levelling technique in data-flow diagrams is adapted in the refinement and the abstraction techniques, and the state decomposition idea in state-charts is employed in designing various label formulation operators. The methodology is illustrated through the specification of a lift system. The methodology can significantly reduce the constructing complexity and enhance the comprehensibility of large predicate transition net specifications.
14270830
Laplacian Score for Feature Selection
In supervised learning scenarios, feature selection has been studied widely in the literature. Selecting features in unsupervised learning scenarios is a much harder problem, due to the absence of class labels that would guide the search for relevant information. And, almost all of previous unsupervised feature selection methods are "wrapper" techniques that require a learning algorithm to evaluate the candidate feature subsets. In this paper, we propose a "filter" method for feature selection which is independent of any learning algorithm. Our method can be performed in either supervised or unsupervised fashion. The proposed method is based on the observation that, in many real world classification problems, data from the same class are often close to each other. The importance of a feature is evaluated by its power of locality preserving, or, Laplacian Score. We compare our method with data variance (unsupervised) and Fisher score (supervised) on two data sets. Experimental results demonstrate the effectiveness and efficiency of our algorithm.
8216313
Locality preserving indexing for document representation
Document representation and indexing is a key problem for document analysis and processing, such as clustering, classification and retrieval. Conventionally, Latent Semantic Indexing (LSI) is considered effective in deriving such an indexing. LSI essentially detects the most representative features for document representation rather than the most discriminative features. Therefore, LSI might not be optimal in discriminating documents with different semantics. In this paper, a novel algorithm called Locality Preserving Indexing (LPI) is proposed for document indexing. Each document is represented by a vector with low dimensionality. In contrast to LSI which discovers the global structure of the document space, LPI discovers the local structure and obtains a compact document representation subspace that best detects the essential semantic structure. We compare the proposed LPI approach with LSI on two standard databases. Experimental results show that LPI provides better representation in the sense of semantic structure.
39496103
An Application of Well-orderly Trees in Graph Drawing
Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height , which can be constructed in linear time. This improves the best previous bound of .
6559152
Tensor space model for document analysis
Vector Space Model (VSM) has been at the core of information retrieval for the past decades. VSM considers the documents as vectors in high dimensional space.In such a vector space, techniques like Latent Semantic Indexing (LSI), Support Vector Machines (SVM), Naive Bayes, etc., can be then applied for indexing and classification. However, in some cases, the dimensionality of the document space might be extremely large, which makes these techniques infeasible due to the curse of dimensionality. In this paper, we propose a novel Tensor Space Model for document analysis. We represent documents as the second order tensors, or matrices. Correspondingly, a novel indexing algorithm called Tensor Latent Semantic Indexing (TensorLSI) is developed in the tensor space. Our theoretical analysis shows that TensorLSI is much more computationally efficient than the conventional Latent Semantic Indexing, which makes it applicable for extremely large scale data set. Several experimental results on standard document data sets demonstrate the efficiency and effectiveness of our algorithm.
1473802
Locality preserving clustering for image database
It is important and challenging to make the growing image repositories easy to search and browse. Image clustering is a technique that helps in several ways, including image data preprocessing, user interface designing, and search result representation. Spectral clustering method has been one of the most promising clustering methods in the last few years, because it can cluster data with complex structure, and the (near) global optimum is guaranteed. However, existing spectral clustering algorithms, like Normalized Cut, are difficult to handle data points out of training set. In this paper, we propose a clustering algorithm named Locality Preserving Clustering (LPC), which shares many of the data representation properties of nonlinear spectral method. Yet LPC provides an explicit mapping function which is defined everywhere, both on training data points and testing points. Experimental results show that LPC is more accurate than both "direct Kmeans" and "PCA + Kmeans". We also show that LPC produces in general comparable results with Normalized Cut, yet is more efficient than Normalized Cut.