Computer Sciences Commons^™

Beyond Regular : Pattern Matching With Extended Regular Expressions, Benjamin Robert Carle

Legacy Theses & Dissertations (2009 - 2024)

Regular expression pattern matching or some variant thereof is present

Toward A Theory-Based Natural Language Capability In Robots And Other Embodied Agents : Evaluating Hausser's Slim Theory And Database Semantics, Robin Kowalchuk Burk

Legacy Theses & Dissertations (2009 - 2024)

Computational natural language understanding and generation have been a goal of artificial intelligence since McCarthy, Minsky, Rochester and Shannon first proposed to spend the summer of 1956 studying this and related problems. Although statistical approaches dominate current natural language applications, two current research trends bring renewed focus on this goal. The nascent field of artificial general intelligence (AGI) seeks to evolve intelligent agents whose multi-subagent architectures are motivated by neuroscience insights into the modular functional structure of the brain and by cognitive science insights into human learning processes. Rapid advances in cognitive robotics also entail multi-agent software architectures that attempt …

Performance Tuning Of Streaming Applications Via Search-Space Decomposition, Shobana Padmanabhan, Roger D. Chamberlain, Yixin Chen

All Computer Science and Engineering Research

High-performance streaming applications are typically pipelined and deployed on architecturally diverse (hybrid)systems. Developers of such applications are interested in customizing components used, so as to benefit application performance. We present an efficient and automatic technique for design-space exploration of applications in this problem domain. We solve performance tuning as an optimization problem by formulating cost functions using results from queueing theory. This results in a mixed-integer nonlinear optimization problem which is NP-hard. We reduce the search complexity by decomposing the search space. We have developed a domain-specific decomposition technique using topological information of the application embodied in the queueing network …

Global Constructive Optimization Of Vascular Systems, Manfred Georg, Tobias Preusser, Horst K. Hahn

All Computer Science and Engineering Research

We present a framework for the construction of vascular systems based on optimality principles of theoretical physiology. Given the position and flow distribution of end points of a vascular system, we construct the topology and positions of internal nodes to complete the vascular system in a realistic manner. Optimization is driven by intravascular volume minimization with constraints derived from physiological principles. Direct optimization of a vascular system, including topological changes, is used instead of simulating vessel growth. A good initial topology is found by extracting key information from a previously optimized model with less detail. This technique is used iteratively …

Sorting As A Streaming Application Executing On Chip Multiprocessors, Roger D. Chamberlain, Greg A. Galloway, Mark A. Franklin

All Computer Science and Engineering Research

Expressing concurrency in applications has always been a difficult and error-prone endeavor, yet effective utilization of multi-core processors requires that the concurrency in applications be understood. One approach to the expression of concurrency is streaming, which has shown real promise as a safe and effective method for many application classes. Here, we express a classic problem, sorting, in the streaming paradigm and explore the implications of various algorithm and architectural design parameters on the performance of the application.

Priority Assignment For Real-Time Flows In Wirelesshart Sensor-Actuator Networks, Abusayeed Saifullah, You Chenyang, Yixin Chen

All Computer Science and Engineering Research

Recent years have witnessed the adoption of wireless sensor-actuator networks as a communication infrastructure for process control applications. An important enabling technology for industrial process control is WirelessHART, an open wireless sensor-actuator network standard specifically developed for process industries. A key challenge faced byWirelessHART networks is to meet the stringent real-time communication requirements imposed by feedback control systems in process industries. Fixed priority scheduling, a popular scheduling policy in real-time networks, has recently been shown to be an effective real-time transmission scheduling policy in WirelessHART networks. Priority assignment has a major impact on the schedulability of real-time flows in these …

End-To-End Delay Analysis For Fixed Priority Scheduling In Wirelesshart Networks, Abusayeed Saifullah, You Xu, Chenyang Lu, Yixin Chen

All Computer Science and Engineering Research

The WirelessHART standard has been specifically designed for real-time communication between sensor and actuator devices for industrial process monitoring and control. End-to-end communication delay analysis for WirelessHART networks is required for acceptance test of real-time data flows from sensors to actuators and for workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We, then, exploit the response time analysis for multiprocessor scheduling and propose a novel method for the end-to-end delay analysis of the real-time flows that are scheduled using a fixed …

Split And Merge Functions For Supporting Multiple Processing Pipelines In Mercury Blastn, Jwalant Ahir, Jeremy Buhler, Roger D. Chamberlain

All Computer Science and Engineering Research

Biosequence similarity search is an important application in computational biology. Mercury BLASTN, an FPGA-based implementation of BLAST for DNA, is one of the alternatives for fast DNA sequence comparison. The re-design of BLAST into a streaming application combined with a high-throughput hardware pipeline have enabled Mercury BLAST to emerge as one of the fastest implementations of bio-sequence similarity search. This performance can be further enhanced by exploiting the data-level parallelism present within the application. Here we present a multiple FPGA-based Mercury BLASTN design in order to double the speed and throughput of DNA sequence computation. This paper describes a dual …

Toward A Two-Tier Clinical Warning System For Hospitalized Patients, Gregory Hackmann, Minmin Chen, Octav Chipara, Chenyang Lu, Yixin Chen, Marin Kollef, Thomas C. Bailey

All Computer Science and Engineering Research

Clinical study has found early detection and intervention to be essential for preventing clinical deterioration in patients at general hospital units. In this paper, we envision a two-tiered early warning system designed to identify the signs of clinical deterioration and provide early warning of serious clinical events. The first tier of the system automatically identifies patients at risk of clinical deterioration from existing electronic medical record databases. The second tier performs real-time clinical event detection based on real-time vital sign data collected from on-body wireless sensors attached to those high-risk patients. We employ machine-learning techniques to analyze data from both …

Optimal Design-Space Exploration Of Streaming Applications, Shobana Padmanabhan, Yixin Chen, Roger D. Chamberlain

All Computer Science and Engineering Research

Many embedded and scientific applications are frequently pipelined asynchronously and deployed on architecturally diverse systems to meet performance requirements and resource constraints. We call such pipelined applications streaming applications. Typically, there are several design parameters in the algorithms and architectures used that, when customized, impact the tradeoff between different metrics of application performance as well as resource utilization. Automatic exploration of this design space is the goal of this research. When using architecturally diverse systems to accelerate streaming applications, the design search space is often complex. We present a global optimization framework comprising a novel domain-specific variation of branch-and-bound that …

An Inexpensive Robot Platform For Teleoperation And Experimentation, Daniel A. Lazewatsky, William D. Smart

All Computer Science and Engineering Research

Most commercially-available robots are either aimed at the research community, or are designed with a single purpose in mind. The extensive hobbyist community has tended to focus on the hardware and the low-level software aspects. We claim that there is a need for a low-cost, general-purpose robot, accessible to the hobbyist community, with sufficient computation and sensing to run ``research-grade'' software. In this paper, we describe the design and implementation of such a robot. We explicitly outline our design goals, and show how a capable robot can be assembled from off-the-shelf parts, for a modest cost, by a single person …

Against All Probabilities: A Modeling Paradigm For Streaming Applications That Goes Against Common Notions, Rahav Dor

All Computer Science and Engineering Research

Hardware and software design requires the right portion of skills and mental faculties. The design of a good system is an exercise in rational thinking, engineering, and art. The design process is further complicated when we aspire to build systems that exploit parallelism or are targeted to be deployed on architecturally diverse computing devices, FPGAs or GPUs to name just a few. The need to develop systems that can take advantage of computing devices beyond general purpose CPUs is real. There are several application domains and research efforts that will simply not be able to adequately perform or yield answers …

Arch: Practical Channel Hopping For Reliable Home-Area Sensor Networks, Mo Sha, Gregory Hackmann, Chenyang Lu

All Computer Science and Engineering Research

Home area networks (HANs) promise to enable sophisticated home automation applications such as smart energy usage and assisted living. However, recent empirical study of HAN reliability in real-world residential environments revealed significant challenges to achieving reliable performance in the face of significant and variable interference from a multitude of coexisting wireless devices. We propose the Adaptive and Robust Channel Hopping (ARCH) protocol: a lightweight receiveroriented protocol which handles the dynamics of residential environments by reactively channel hopping when channel conditions have degraded. ARCH has several key features. First, ARCH is an adaptive protocol that channel-hops based on changes in channel …

Multi-Channel Reliability And Spectrum Usage In Real Homes: Empirical Studies For Home-Area Sensor Networks, Mo Sha, Gregory Hackmann, Chenyang Lu

All Computer Science and Engineering Research

Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy and assisted living. A key challenge faced by HANs is maintaining reliable operation in real-world residential environments. This paper presents two in-depth empirical studies on the wireless channels in real homes. The spectrum study analyzes the spectrum usage in the 2.4 GHz band where wireless sensor networks based on the IEEE 802.15.4 standard must coexist with existing wireless devices. We characterize the ambient wireless environment in six apartments through passive spectrum analysis across the entire 2.4 GHz band over …

The Design And Implementation Of Mcflow: A Real-Time Multi-Core Aware Middleware For Dependent Task Graphs, Huang-Ming Huang, Christopher Gill, Chenyang Lu

All Computer Science and Engineering Research

Modern computer architectures have evolved from uni-processor platforms to multi-processor and multi-core plat- forms, but traditional real-time distributed middleware such as RT-CORBA has not kept pace with that evolution. To address those issues, this paper describes the design and implementation of MCFlow, a new real-time distributed middleware for dependent task graphs running on multi-core platforms. MCFlow provides the following contributions to the state of the art in real-time middleware: (1) it provides an efficient C++ based component model through which computations can be configured flexibly for execution within a single core, across cores of a common host, or spanning multiple …

What Do Collaborations With The Arts Have To Say About Human-Robot Interaction?, William D. Smart, Annamaria Pileggi, Leila Takayama

All Computer Science and Engineering Research

This is a collection of papers presented at the workshop "What Do Collaborations with the Arts Have to Say About HRI", held at the 2010 Human-Robot Interaction Conference, in Osaka, Japan.

Multi-Tier Diversified Service Architecture For Internet 3.0: The Next Generation Internet, Subharthi Paul, Raj Jain, Jianli Pan, Chakchai So-In

All Computer Science and Engineering Research

The next generation Internet needs to support multiple diverse application contexts. In this paper, we present Internet 3.0, a diversified, multi-tier architecture for the next generation Internet. Unlike the current Internet, Internet 3.0 defines a new set of primitives that allows diverse applications to compose and optimize their specific contexts over resources belonging to multiple ownerships. The key design philosophy is to enable diversity through explicit representation, negotiation and enforcement of policies at the granularity of network infrastructure, compute resources, data and users. The basis of the Internet 3.0 architecture is a generalized three-tier object model. The bottom tier consists …

Preface, Berthe Y. Choueiry, Bob Givan

School of Computing: Conference and Workshop Papers

The Tenth International Symposium on Artificial Intelligence and Mathematics (ISAIM 2008) gathered a fine and distinguished crowd of researchers active in mathematics, theoretical computer science, and artificial intelligence. The three-day meeting, held from January 2 to 4, 2008, in Fort Lauderdale, featured invited talks by keynote speakers David McAllester, Francesca Rossi and Naftali Tishby. The program also included special sessions on “Computation and Social Choice” (organized by Toby Walsh), “Effective Exploration in Active Learning and Reinforcement Learning” (organized by Pascal Poupart), and “Logic in Artificial Intelligence” (organized by Michael Kaminski and Miroslaw Truszczynski, and the subject of a separate special …

A First Practical Algorithm For High Levels Of Relational Consistency, Shant Karakashian, Robert J. Woodward, Christopher Reeson, Berthe Y. Choueiry, Christian Bessiere

School of Computing: Conference and Workshop Papers

•Introduction

•Relational Consistency R(*,m)C :

–Definition, Naïve algorithm, Properties

•Preliminaries: Dual CSP

•Our Approach

–Algorithm

–Index-Tree Data Structure

–Advantages

•A weakened version of R(*,m)C: wR(*,m)C

•Experimental Evaluations

•Conclusions & Future Work

Cloud Computing For Scalable Planning By Stochastic Search, Qiang Lu, You Xu, Ruoyun Huang, Yixin Chen

All Computer Science and Engineering Research

Graph search has been employed by many AI techniques and applications. A natural way to improve the efficiency of search is to utilize ad- vanced, more powerful computing platforms. However, expensive computing infrastructures, such as supercomputers and large-scale clusters, are traditionally available to only a limited number of projects and researchers. As a results, most AI applications, with access to only commodity com- puters and clusters, cannot benefit from the efficiency improvements of high-performance parallel search algorithms. Cloud computing provides an attractive, highly accessible alternative to other traditional high- performance computing platforms. In this paper, we first show that the …

Optimal Time Utility Based Scheduling Policy Design For Cyber-Physical Systems , Terry Tidwell, Robert Glaubius, Christopher D. Gill, William D. Smart

All Computer Science and Engineering Research

Classical scheduling abstractions such as deadlines and priorities do not readily capture the complex timing semantics found in many real-time cyber-physical systems. Time utility functions provide a necessarily richer description of timing semantics, but designing utility-aware scheduling policies using them is an open research problem. In particular, optimal utility accrual scheduling design is needed for real-time cyber-physical domains. In this paper we design optimal utility accrual scheduling policies for cyber-physical systems with periodic, non-preemptable tasks that run with stochastic duration. These policies are derived by solving a Markov Decision Process formulation of the scheduling problem. We use this formulation to …

A Front-End For An Ownership Object Graph Interactive Editor, Talia Frances Selitsky

Wayne State University Theses

Runtime views which show runtime structure, is a type of object graph. They show components as groups of objects and data structures. Runtime views are useful for tasks related to performance, reliability, and security. Most previous work on extracting object graphs has produced flat object graphs which are not scalable. Ownership object graphs (OOGs) increase the scalability of object graphs because it nests objects, creating hierarchy. Recent work has shown that sound extraction of OOGs from object-oriented systems is technically feasible. Soundness means that in any execution of the program, every object can be mapped to exactly one component in …

Choosing Between Remote I/O Versus Staging In Distributed Environments, Ibrahim Hakki Suslu

LSU Doctoral Dissertations

Today, scientifi_x000C_c applications and experiments have become increasingly complex and more demanding in terms of their computational and data requirements. The amount of data generated and used has grown at a very rapid rate. As tens or hundreds of terabytes of data for a single application is very common today; petabytes and even exabytes of data will be very common in a few years. One of the major challenges in distributed computing environments is how to access these large datasets remotely over the network. Data staging and remote I/O are the most widely used data access methods for distributed applications. …

A Reasonable Semantic Web, Pascal Hitzler, Frank Van Harmelen

Computer Science and Engineering Faculty Publications

The realization of Semantic Web reasoning is central to substantiating the Semantic Web vision. However, current mainstream research on this topic faces serious challenges, which forces us to question established lines of research and to rethink the underlying approaches. We argue that reasoning for the Semantic Web should be understood as "shared inference," which is not necessarily based on deductive methods. Model-theoretic semantics (and sound and complete reasoning based on it) functions as a gold standard, but applications dealing with large-scale and noisy data usually cannot afford the required runtimes. Approximate methods, including deductive ones, but also approaches based on …

Automated Isolation Of Translational Efficiency Bias That Resists The Confounding Effect Of Gc(At)-Content, Douglas W. Raiford, Dan E. Krane, Travis E. Doom, Michael L. Raymer

Kno.e.sis Publications

Genomic sequencing projects are an abundant source of information for biological studies ranging from the molecular to the ecological in scale; however, much of the information present may yet be hidden from casual analysis. One such information domain, trends in codon usage, can provide a wealth of information about an organism's genes and their expression. Degeneracy in the genetic code allows more than one triplet codon to code for the same amino acid, and usage of these codons is often biased such that one or more of these synonymous codons is preferred. Detection of this bias is an important tool …

Linked Open Social Signals, Pablo N. Mendes, Alexandre Passant, Pavan Kapanipathi, Amit P. Sheth

Kno.e.sis Publications

In this paper we discuss the collection, semantic annotation and analysis of real-time social signals from micro-blogging data. We focus on users interested in analyzing social signals collectively for sensemaking. Our proposal enables flexibility in selecting subsets for analysis, alleviating information overload. We define an architecture that is based on state-of-the-art Semantic Web technologies and a distributed publish subscribe protocol for real time communication. In addition, we discuss our method and application in a scenario related to the health care reform in the United States.

Continuous Semantics To Analyze Real-Time Data, Amit P. Sheth, Christopher Thomas, Pankaj Mehra

Kno.e.sis Publications

Increasingly we are presented with dynamic domains involved in social, mobile, and sensor webs. Such domains are spontaneous (arising suddenly), follow a period of rapid evolution, involving real-time or near real-time data, involve many distributed participants and diverse viewpoints involving topical or contentious subjects, and involve feature context colored by local knowledge and sociocultural backgrounds. This article present continuous semantics can help us model such dynamic domains and analyze the related real-time data. Capabilities include crating dynamic domain model by mining social data, and using dynamic models for semantic analysis of real-time data.

A Metric For Routing In Delay-Sensitive Wireless Sensor Networks, Zhen Jiang, Jie Wu, Risa Ito

Computer Science Faculty Publications

No abstract provided.

Cr: Capability Information For Routing Of Wireless Ad Hoc Networks In The Real Environment, Zhen Jiang, Zhigang Li, Nong Xiao, Jie Wu

Computer Science Faculty Publications

No abstract provided.

Optimal Control Of Affine Nonlinear Continuous-Time Systems Using An Online Hamilton-Jacobi-Isaacs Formulation, T. Dierks, Sarangapani Jagannathan

Electrical and Computer Engineering Faculty Research & Creative Works

Solving the Hamilton-Jacobi-Isaacs (HJI) equation, commonly used in ℋ∞ optimal control, is often referred to as a two-player differential game where one player tries to minimize the cost function while the other tries to maximize it. in this paper, the HJI equation is formulated online and forward-in-time using a novel single online approximator (SOLA)-Based scheme to achieve optimal regulation and tracking control of affine nonlinear continuous-time systems. the SOLA-Based adaptive approach is designed to learn the infinite horizon HJI equation, the corresponding optimal control input, and the worst-case disturbance. a novel parameter tuning algorithm is derived which not only achieves …