A Hoare Calculus For Graph Programs,
2010
Singapore Management University
A Hoare Calculus For Graph Programs, Christopher M. Poskitt, Detlef Plump
Research Collection School Of Computing and Information Systems
We present Hoare-style axiom schemata and inference rules for verifying the partial correctness of programs in the graph programming language GP. The pre- and postconditions of this calculus are the nested conditions of Habel, Pennemann and Rensink, extended with expressions for labels in order to deal with GP’s conditional rule schemata and infinite label alphabet. We show that the proof rules are sound with respect to GP’s operational semantics.
Hoare Logic For Graph Programs,
2010
Singapore Management University
Hoare Logic For Graph Programs, Christopher M. Poskitt, Detlef Plump
Research Collection School Of Computing and Information Systems
We present a new approach for verifying programs written in GP (for Graph Programs), an experimental programming language for performing computations on graphs at a high level of abstraction. Taking a labelled graph as input, a graph program nondeterministically applies to it a number of graph transformation rules, directed by simple control constructs such as sequential composition and as-long-as-possible iteration. We adapt classical Hoare logic to the domain of graphs, and describe a system of sound proof rules for showing the partial correctness of graph programs.
On Decision Support For Deliberating With Constraints In Constrained Optimization Models,
2010
Singapore Management University
On Decision Support For Deliberating With Constraints In Constrained Optimization Models, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau, David H. Wood
Research Collection School Of Computing and Information Systems
This paper introduces the Deliberation Decision Support System (DDSS). The DDSS obtains heuristically (using a genetic algorithm) solutions of interest for constrained optimization models. This is illustrated, without loss of generality, by generalized assignment problems. The DDSS also provides users with graphical tools that support post-solution deliberation for constrained optimization models. The DDSS and this paper, as befits practical concerns, are focused on deliberation with respect to the constraints of the models being used.
Semi-Supervised Distance Metric Learning For Collaborative Image Retrieval And Clustering,
2010
Singapore Management University
Semi-Supervised Distance Metric Learning For Collaborative Image Retrieval And Clustering, Steven C. H. Hoi, Wei Liu, Shih-Fu Chang
Research Collection School Of Computing and Information Systems
Learning a good distance metric plays a vital role in many multimedia retrieval and data mining tasks. For example, a typical content-based image retrieval (CBIR) system often relies on an effective distance metric to measure similarity between any two images. Conventional CBIR systems simply adopting Euclidean distance metric often fail to return satisfactory results mainly due to the well-known semantic gap challenge. In this article, we present a novel framework of Semi-Supervised Distance Metric Learning for learning effective distance metrics by exploring the historical relevance feedback log data of a CBIR system and utilizing unlabeled data when log data are …
Merging Schemas In A Collaborative Faceted Classification System,
2010
Old Dominion University
Merging Schemas In A Collaborative Faceted Classification System, Jianxiang Li
Computer Science Theses & Dissertations
We have developed a system that improves access to a large, growing image collection by allowing users to collaboratively build a global faceted (multi-perspective) classification schema. We are extending our system to support both global and local schemas, where global schema provides a complete and uniform view of the collection whereas local schema provides a personal, possibly incomplete and idiosyncratic view of the collection. We argue that although users usually focus on their personal schemas, it is still desirable to have a global schema for the entire collection even if such local schemas are available. In order to keep the …
Cloud Storage And Online Bin Packing,
2010
University of Nevada, Las Vegas
Cloud Storage And Online Bin Packing, Swathi Venigella
UNLV Theses, Dissertations, Professional Papers, and Capstones
Cloud storage is the service provided by some corporations (such as Mozy and Carbonite) to store and backup computer files. We study the problem of allocating memory of servers in a data center based on online requests for storage. Over-the-net data backup has become increasingly easy and cheap due to cloud storage. Given an online sequence of storage requests and a cost associated with serving the request by allocating space on a certain server one seeks to select the minimum number of servers as to minimize total cost. We use two different algorithms and propose a third algorithm; we show …
Detours Admitting Short Paths,
2010
University of Nevada, Las Vegas
Detours Admitting Short Paths, Reshma Koganti
UNLV Theses, Dissertations, Professional Papers, and Capstones
Finding shortest paths between two vertices in a weighted graph is a well explored problem and several efficient algorithms for solving it have been reported. We propose a new variation of this problem which we call the Detour Admitting Shortest Path Problem (DASPP).We present an efficient algorithm for solving DASPP. This is the first algorithm that constructs a shortest path such that each edge of the shortest path admits a detour with no more than k−hops. This algorithm has important applications in transportation networks. We also present implementation issues for the detour admitting shortest path algorithm.
A First Practical Algorithm For High Levels Of Relational Consistency,
2010
University of Nebraska-Lincoln
A First Practical Algorithm For High Levels Of Relational Consistency, Shant Karakashian, Robert J. Woodward, Christopher Reesons, Berthe Y. Choueiry, Christian Bessiere
School of Computing: Conference and Workshop Papers
Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. In this paper, we study the relational consistency property R(∗,m)C, which is equivalent to m-wise consistency proposed in relational databases. We also define wR(∗,m)C, a weaker variant of this property. We propose an algorithm for enforcing these properties on a Constraint Satisfaction Problem by tightening the existing relations and without introducing new ones. We empirically show that wR(∗,m)C solves in a backtrack-free manner all the instances of some CSP benchmark classes, thus hinting at the tractability of those classes.
Action Recognition Based On Multi-Level Representation Of 3d Shape,
2010
Old Dominion University
Action Recognition Based On Multi-Level Representation Of 3d Shape, Binu M. Nair
Electrical & Computer Engineering Theses & Dissertations
A novel algorithm is proposed in this thesis for recognizing human actions using a combination of two shape descriptors, one of which is a 3D Euclidean distance transform and the other based on the Radon transform. This combination captures the necessary variations from the space time shape for recognizing actions. The space time shapes are created by the concatenation of human body silhouettes across time. The comparisons are done against some common shape descriptors such as the zernike moments and Radon transform. This is also compared with an algorithm which uses the same concept of a space time shape and …
A Differential Absorption Model For Remote Sensing Of Atmospheric Pressure,
2010
Old Dominion University
A Differential Absorption Model For Remote Sensing Of Atmospheric Pressure, Shivam J. Shah
Electrical & Computer Engineering Theses & Dissertations
The goal of the project is to develop and test a "model based" radar processing strategy that is compatible with the concept of a "cognitive radar". The basic approach will be to develop a cognitive radar algorithm (genetic algorithm) based on the capabilities of an existing commercially available Software Radio. While the focus of this effort is the development of a candidate approach for genetic algorithm, the longer term goal would be to implement the approach using this software radio technology to provide a low cost radar processor. The proposed technology would use differential absorption radar working at the 50-56 …
An Application Of Automated Theorem Provers To Computer System Security: The Schematic Protection Model,
2010
Air Force Institute of Technology
An Application Of Automated Theorem Provers To Computer System Security: The Schematic Protection Model, Mitchell D.I. Hirschfeld
Theses and Dissertations
The Schematic Protection Model is specified in SAL and theorems about Take-Grant and New Technology File System schemes are proven. Arbitrary systems can be specified in SPM and analyzed. This is the first known automated analysis of SPM specifications in a theorem prover. The SPM specification was created in such a way that new specifications share the underlying framework and are configurable within the specifications file alone. This allows new specifications to be created with ease as demonstrated by the four unique models included within this document. This also allows future users to more easily specify models without recreating the …
Information Hiding Using Stochastic Diffusion For The Covert Transmission Of Encrypted Images,
2010
Technological University Dublin
Information Hiding Using Stochastic Diffusion For The Covert Transmission Of Encrypted Images, Jonathan Blackledge
Conference papers
A principal weakness of all encryption systems is that the output data can be `seen' to be encrypted. In other words, encrypted data provides a 'flag' on the potential value of the information that has been encrypted. In this paper, we provide a novel approach to `hiding' encrypted data in a digital image. We consider an approach in which a plaintext image is encrypted with a cipher using the processes of `stochastic diffusion' and the output quantized into a 1-bit array generating a binary image cipher-text. This output is then `embedded' in a host image which is undertaken either in …
Generating Compact Wasp Nest Structures Via Minimal Complexity Algorithms.,
2010
East Tennessee State University
Generating Compact Wasp Nest Structures Via Minimal Complexity Algorithms., Fadel Ewusi Kofi Adoe
Electronic Theses and Dissertations
Many models have been developed to explain the process of self organization-the emergence of seemingly purposeful behaviors from groups of entities with limited individual intelligence. However, the underlying behavior that facilitates the emergence of this global pattern is not generally well understood. Our study focuses on different low complexity building algorithms and characterizes how nests are built using these algorithms. Three rules postulated to be functions of wasps' building behavior were developed. First is the random rule, in which there is no constraint per the choice of site to be initiated. The second is the 2-cell rule where only sites …
Personalization By Website Transformation: Theory And Practice,
2010
University of Dayton
Personalization By Website Transformation: Theory And Practice, Saverio Perugini
Computer Science Faculty Publications
We present an analysis of a progressive series of out-of-turn transformations on a hierarchical website to personalize a user’s interaction with the site. We formalize the transformation in graph-theoretic terms and describe a toolkit we built that enumerates all of the traversals enabled by every possible complete series of these transformations in any site and computes a variety of metrics while simulating each traversal therein to qualify the relationship between a site’s structure and the cumulative effect of support for the transformation in a site. We employed this toolkit in two websites. The results indicate that the transformation enables users …
Open Innovation In Platform Competition,
2010
Singapore Management University
Open Innovation In Platform Competition, Mei Lin
Research Collection School Of Computing and Information Systems
We examine the competition between a proprietary platform and an open platform,where each platform holds a two-sided market consisted of app developers and users.The open platform cultivates an innovative environment by inviting public efforts todevelop the platform itself and permitting distribution of apps outside of its own appmarket; the proprietary platform restricts apps sales solely within its app market. Weuse a game theoretic model to capture this competitive phenomenon and analyze theimpact of growth of the open source community on the platform competition. We foundthat growth of the open community mitigates the platform rivalry, and balances the developernetwork sizes on …
A Genetic Algorithm Approach For Optimized Routing,
2010
Old Dominion University
A Genetic Algorithm Approach For Optimized Routing, Pavithra Gudur
Electrical & Computer Engineering Theses & Dissertations
Genetic Algorithms find several applications in a variety of fields, such as engineering, management, finance, chemistry, scheduling, data mining and so on, where optimization plays a key role. This technique represents a numerical optimization technique that is modeled after the natural process of selection based on the Darwinian principle of evolution. The Genetic Algorithm (GA) is one among several optimization techniques and attempts to obtain the desired solution by generating a set of possible candidate solutions or populations. These populations are then compared and the best solutions from the set are retained. Subsequently, new candidate solutions are produced, and the …
Finding Influentials Based On The Temporal Order Of Information Adoption In Twitter,
2010
Singapore Management University
Finding Influentials Based On The Temporal Order Of Information Adoption In Twitter, Changhyun Lee, Haewoon Kwak, Hosung Park, Sue Moon
Research Collection School Of Computing and Information Systems
Twitter offers an explicit mechanism to facilitate information diffusion and has emerged as a new medium for communication. Many approaches to find influentials have been proposed, but they do not consider the temporal order of information adoption. In this work, we propose a novel method to find influentials by considering both the link structure and the temporal order of information adoption in Twitter. Our method finds distinct influentials who are not discovered by other methods.
Expression Invariant Face Recognition Using Shifted Phase-Encoded Joint Transform Correlation Technique,
2010
Old Dominion University
Expression Invariant Face Recognition Using Shifted Phase-Encoded Joint Transform Correlation Technique, Trisha Ahmed
Electrical & Computer Engineering Theses & Dissertations
A new face recognition algorithm using a synthetic discriminant function based shifted phase-encoded fringe-adjusted joint transform correlation (SDF-SPFJTC) technique is proposed. The dark region in an input image is enhanced by using a nonlinear technique named ratio enhancement in gaussian neighborhood (REIGN). Histogram equalization and Gaussian smoothing are then performed to the enhanced face images and the synthetic discriminant function (SDF) image before they are subjected to the joint transform correlation process. The two distinct correlation peaks produced on extreme ends of the SPFJTC plane signifies the recognition of a potential target. A post processing step utilizes the peak-to-clutter ratio …
Evolutionary Artificial Neural Network Weight Tuning To Optimize Decision Making For An Abstract Game,
2010
Air Force Institute of Technology
Evolutionary Artificial Neural Network Weight Tuning To Optimize Decision Making For An Abstract Game, Corey M. Miller
Theses and Dissertations
Abstract strategy games present a deterministic perfect information environment with which to test the strategic capabilities of artificial intelligence systems. With no unknowns or random elements, only the competitors’ performances impact the results. This thesis takes one such game, Lines of Action, and attempts to develop a competitive heuristic. Due to the complexity of Lines of Action, artificial neural networks are utilized to model the relative values of board states. An application, pLoGANN (Parallel Lines of Action with Genetic Algorithm and Neural Networks), is developed to train the weights of this neural network by implementing a genetic algorithm over a …
Handshaking Protocols And Jamming Mechanisms For Blind Rendezvous In A Dynamic Spectrum Access Environment,
2010
Air Force Institute of Technology
Handshaking Protocols And Jamming Mechanisms For Blind Rendezvous In A Dynamic Spectrum Access Environment, Aaron A. Gross
Theses and Dissertations
Blind frequency rendezvous is an important process for bootstrapping communications between radios without the use of pre-existing infrastructure or common control channel in a Dynamic Spectrum Access (DSA) environment. In this process, radios attempt to arrive in the same frequency channel and recognize each other’s presence in changing, under-utilized spectrum. This paper refines existing blind rendezvous techniques by introducing a handshaking algorithm for setting up communications once two radios have arrived in the same frequency channel. It then investigates the effect of different jamming techniques on blind rendezvous algorithms that utilize this handshake. The handshake performance is measured by determining …
