Computer Sciences Commons^™

Autoreducibility, Mitoticity, And Immunity, Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

Computer Science Faculty Publications

We show the following results regarding complete sets. • NP-complete sets and PSPACE-complete sets are polynomial-time many–one autoreducible.

• Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are polynomial-time many–one autoreducible.

• EXP-complete sets are polynomial-time many–one mitotic.

• If there is a tally language in NP ∩ coNP − P , then, for every ϵ > 0 , NP-complete sets are not 2 n ( 1 + ϵ ) -immune.

These results solve several of the open questions raised by Buhrman and Torenvliet in their 1994 survey paper on the structure of complete sets.

A Model For Managing Decision-Making Information In The Gig-Enabled Battlespace, Samuel D. Bass, Rusty O. Baldwin

Computer Science Faculty Publications

The Defense Department is transforming information-technology systems into a Global Information Grid (GIG) that will connect sensors to weapons systems and provide unprecedented situational awareness. The authors suggest that if not properly implemented, the GIG may overwhelm war fighters with information presented at the wrong time, at the wrong level of detail, and without proper analysis. This article proposes a model to direct the flow of information in the GIG.

Hierarchical Collective Agent Network (Hcan) For Efficient 3 Fusion And Management Of Multiple Networked Sensors, Qiuming Zhu, Stuart L. Aldridge, Tomas N. Resha

Computer Science Faculty Publications

Agent-based software systems and applications are constructed by integrating diverse sets of components that are intelligent, heterogeneous, distributed, and concurrent. This paper describes a multi-agent system to assure the operation efficiency and reliability in data fusion and management of a set of networked distributive sensors (NDS). We discuss the general concept and architecture of a Hierarchical Collective Agent Network (HCAN) and its functional components for learning and adaptive control of the NDS. Sophistication of a HCAN control environment and an anatomy of the agent modules for enabling intelligent data fusion and management are presented. An exemplar HCAN is configured to …

Factors Affecting Website Reconstruction From The Web Infrastructure, Frank Mccown, Norou Diawara, Michael L. Nelson

Computer Science Faculty Publications

When a website is suddenly lost without a backup, it may be reconstituted by probing web archives and search engine caches for missing content. In this paper we describe an experiment where we crawled and reconstructed 300 randomly selected websites on a weekly basis for 14 weeks. The reconstructions were performed using our web-repository crawler named Warrick which recovers missing resources from the Web Infrastructure (WI), the collective preservation effort of web archives and search engine caches. We examine several characteristics of the websites over time including birth rate, decay and age of resources. We evaluate the reconstructions when compared …

Residual-Based Measurement Of Peer And Link Lifetimes In Gnutella Networks, Xiaoming Wang, Zhongmei Yao, Dmitri Loguinov

Computer Science Faculty Publications

Existing methods of measuring lifetimes in P2P systems usually rely on the so-called create-based method (CBM), which divides a given observation window into two halves and samples users "created" in the first half every Delta time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we flrst derive a model for CBM and show that small window size or large Delta may lead to highly inaccurate lifetime distributions. We then show that create-based sampling exhibits an inherent …

On Node Isolation Under Churn In Unstructured P2p Networks With Heavy-Tailed Lifetimes, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov

Computer Science Faculty Publications

Previous analytical studies [12], [18] of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared to uniform selection of neighbors. In fact, the second strategy based on random walks on age-weighted graphs demonstrates that for lifetimes with infinite variance, the system …

Cmodels: Sat-Based Answer Set Programming System, Yuliya Lierler, Marco Maratea

Computer Science Faculty Publications

CMODELS [1, 2] is an answer set programming [3] system that uses the same frontend LPARSE as answer set solver SMODELS (http://www.tcs.hut.fi/Software/smodels/). CMODELS main computational characteristics is that it computes answer sets using a SAT solver for search.

The use of SAT solvers for generating answer sets is based on the fact that for logic programs satisfying syntactic condition, tightness, the answer set semantics is equivalent to the Clark’s completion semantics. In addition, [4] introduced concept of a loop formula, and demonstrated that the answer sets of a logic program are exactly the models of its completion that satisfy the …

Atmospheric Scaling Of Cosmogenic Nuclide Production: Climate Effect, Jane Staiger, John Gosse, Rick Toracinta, Bob Oglesby, James Fastook, Jesse V. Johnson

Computer Science Faculty Publications

Absorption of cosmic rays by atmospheric mass varies temporally due to a redistribution of atmospheric pressure by ice sheets during glaciations, the compression and expansion of the atmosphere due to cooling and warming, and changes in katabatic winds near large ice masses. These atmospheric processes can result in changes in production rates of cosmogenic nuclides which, when integrated over long exposure durations may result in 0% to >5% adjustments in site production rates depending on location. Combining a CCM3 model with imbedded ice sheets for 20 ka, we show that production rates changes (relative to today) are greatest at high …

Modeling Long-Term Stability Of The Ferrar Glacier, East Antarctica: Implications For Interpreting Cosmogenic Nuclide Inheritance, Jesse V. Johnson, Jane W. Staiger

Computer Science Faculty Publications

The Ferrar Glacier extends from the Taylor Dome, through the Royal Society Range, to the Ross Sea. Its pathway is strongly influenced by large-scale topographic features. Ice thins and flows over these features, like water over a dam. Recently acquired evidence demonstrates that the profile of the Ferrar Glacier has been relatively static for the last 4 million years. This long record of stability is in sharp contrast to numerous other features in Antarctica and motivates an exploration of the stability with a numerical model. Large variations in ice thickness along the Ferrar profile make necessary a thermomechanically coupled model …

Topology Control For Secured Coverage In Wireless Sensor Networks, Zhen Jiang, Jie Wu, Afrand Agah, Bin Lu

Computer Science Faculty Publications

No abstract provided.

A Study Of Out-Of-Turn Interaction In Menu-Based, Ivr, Voicemail Systems, Saverio Perugini, Taylor J. Anderson, William F. Moroney

Computer Science Faculty Publications

We present the first user study of out-of-turn interaction in menu-based, interactive voice-response systems. Out-ofturn interaction is a technique which empowers the user (unable to respond to the current prompt) to take the conversational initiative by supplying information that is currently unsolicited, but expected later in the dialog. The technique permits the user to circumvent any flows of navigation hardwired into the design and navigate the menus in a manner which reflects their model of the task. We conducted a laboratory experiment to measure the effect of the use of outof- turn interaction on user performance and preference in a …

On Achieving The Shortest-Path Routing In 2-D Meshes, Zhen Jiang, Jie Wu

Computer Science Faculty Publications

No abstract provided.

Wireless And Sensor Networks Security (Wsns): A Retrospection, Falko Dressler, Yong Guan, Zhen Jiang

Computer Science Faculty Publications

No abstract provided.

Quantifying Position Accuracy Of Multimodal Data From Global Positioning System–Enabled Cell Phones, David P. Aguilar, Sean J. Barbeau, Miguel A. Labrador, Alfredo J. Perez, Rafael A. Perez

Computer Science Faculty Publications

The emergence of cell phones with embedded Global Positioning System (GPS) chips provides opportunities to push personalized real-time travel information subject to an individual's current location. One such application, a travel assistant device, notifies cognitively disabled public transportation users when it is time to request a stop and exit the vehicle. GPS-enabled cell phones must provide highly accurate real-time location data for this type of service. The components used in the data-collection process are identified, and a quantitative analysis of real-time GPS data obtained with a cell phone while walking, driving a vehicle, and riding public transportation is provided. The …

Optimal Layout Of Multicast Groups Using Network Embedded Multicast Security In Ad Hoc Sensor Networks, Richard R. Brooks, Brijesh Pillai, Michele C. Weigle, Matthew Pirretti

Computer Science Faculty Publications

This paper considers the security of sensor network applications. Our approach creates multicast regions that use symmetric key cryptography for communications. Each multicast region contains a single keyserver that is used to perform key management and maintain the integrity of a multicast region. Communications between two multicast regions is performed by nodes that belong to both regions. To ease the network management burden, it is desirable for the networks to self-organize into regions and dynamically select their keyservers. This paper shows how to determine the number of keyservers (k) to use and the size in the number of hops (h) …

Hybrid Training With Binary Search Protocol For Wireless Sensor Networks, Ruzana Ishak, Qingwen Xu, Stephan Olariu, Shaharuddin Salleh

Computer Science Faculty Publications

Locationing problem in Wireless Sensor Networks(WSN) can be viewed as a general distributed sensor problem. It is with sensors that can discover other nodes or estimate ranges between nodes. that serve as position references. In this paper. we show that sensors acquire coarse-grain location awareness by the training protocol. The training protocol which hybrids the synchronization and training procedure. In this protocol, synchronization and training are combined into one scheme. The sink node sends two beacons in each slot instead of one. In the training, sensor searching for its location using a binary search scheme. Our simulation results shown less …

Istart 2: Improvements For Efficiency And Effectiveness, Irwin B. Levinstein, Chutima Boonthum, Srinivasa P. Pillarisetti, Courtney Bell, Danielle S. Mcnamara

Computer Science Faculty Publications

iSTART (interactive strategy training for active reading and thinking) is a Web-based reading strategy trainer that develops students' ability to self-explain difficult text as a means to improving reading comprehension. Its curriculum consists of modules presented interactively by pedagogical agents: an introduction to the basics of using reading strategies in the context of self-explanation, a demonstration of self-explanation, and a practice module in which the trainee generates self-explanations with feedback on the quality of reading strategies contained in the self-explanations. We discuss the objectives that guided the development of the second version of iSTART toward the goals of increased efficiency …

Assessing The Format Of The Presentation Of Text In Developing A Reading Strategy Assessment Tool (R-Sat), Sara Gilliam, Joseph P. Magliano, Keith K. Millis, Irwin Levinstein, Chutima Boonthum

Computer Science Faculty Publications

We are constructing a new computerized test of reading comprehension called the Reading Strategy Assessment Tool (R-SAT). R-SAT elicits and analyzes verbal protocols that readers generate in response to questions as they read texts. We examined whether the amount of information available to the reader when reading and answering questions influenced the extent to which R-SAT accounts for comprehension. We found that R-SAT was most predictive of comprehension when the readers did not have access to the text as they answered questions.

All Minimal Prime Extensions Of Hereditary Classes Of Graphs, Vassilis Giakoumakis, Stephan Olariu

Computer Science Faculty Publications

The substitution composition of two disjoint graphs G₁ and G₂ is obtained by first removing a vertex x from G₂ and then making every vertex in G₁ adjacent to all neighbours of x in G₂. Let F be a family of graphs defined by a set Z* of forbidden configurations. Giakoumakis [V. Giakoumakis, On the closure of graphs under substitution, Discrete Mathematics 177 (1997) 83–97] proved that F∗, the closure under substitution of F, can be characterized by a set Z∗ of forbidden configurations — the minimal prime extensions of Z. He also …

How Much Preservation Do I Get If I Do Absolutely Nothing? Using The Web Infrastructure For Digital Preservation, Martin Klein, Frank Mccown, Joan A. Smith, Michael Nelson

Computer Science Faculty Publications

To date, most of the focus regarding digital preservation has been on removing copies of the resources to be preserved from the “living web” and placing them in an archive for controlled curation. Once inside an archive, the resources are subject to careful processes of refreshing (making additional copies to new media) and migrating (conversion to new formats and applications). For small numbers of resources of known value, this is a practical and worthwhile approach to digital preservation. However, due to the infrastructure costs (storage, networks, machines) and more importantly the human management costs, this approach is unsuitable for web …

Brass: A Queueing Manager For Warrick, Frank Mccown, Amine Benjelloun, Michael L. Nelson

Computer Science Faculty Publications

When an individual loses their website and a backup can-not be found, they can download and run Warrick, a web-repository crawler which will recover their lost website by crawling the holdings of the Internet Archive and several search engine caches. Running Warrick locally requires some technical know-how, so we have created an on-line queueing system called Brass which simplifies the task of recovering lost websites. We discuss the technical aspects of recon-structing websites and the implementation of Brass. Our newly developed system allows anyone to recover a lost web-site with a few mouse clicks and allows us to track which …

Crate: A Simple Model For Self-Describing Web Resources, Joan A. Smith, Michael L. Nelson

Computer Science Faculty Publications

If not for the Internet Archive’s efforts to store periodic snapshots of the web, many sites would not have any preservation prospects at all. The barrier to entry is too high for everyday web sites, which may have skilled webmasters managing them, but which lack skilled archivists to preserve them. Digital preservation is not easy. One problem is the complexity of preservation models, which have specific meta-data and structural requirements. Another problem is the time and effort it takes to properly prepare digital resources for preservation in the chosen model. In this paper, we propose a simple preservation model called …

Providing Vanet Security Through Active Position Detection, Gongjun Yan, Gyanesh Choudhary, Michele C. Weigle, Stephan Olariu

Computer Science Faculty Publications

Our main contribution is a novel approach to enhancing position security in VANET. We achieve local and global position security by using the on-board radar to detect neighboring vehicles and to confirm their announced coordinates. We compute cosine similarity among data collected by radar and neighbors' reports to filter the forged data from the truthful data. Based on filtered data, we create a history of vehicle movement. By checking the history and computing similarity, we can prevent a large number of Sybil attacks and some combinations of Sybil and position-based attacks.

Modeling Heterogeneous User Churn And Local Resilience Of Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov, Xiaoming Wang

Computer Science Faculty Publications

Previous analytical results on the resilience of unstructured P2P systems have not explicitly modeled heterogeneity of user churn (i.e., difference in online behavior) or the impact of in-degree on system resilience. To overcome these limitations, we introduce a generic model of heterogeneous user churn, derive the distribution of the various metrics observed in prior experimental studies (e.g., lifetime distribution of joining users, joint distribution of session time of alive peers, and residual lifetime of a randomly selected user), derive several closed-form results on the transient behavior of in-degree, and eventually obtain the joint in/out degree isolation probability as a simple …

Pedagogical Possibilities For The N-Puzzle Problem, Zdravko Markov, Ingrid Russell, Todd W. Neller, Neli Zlatareva

Computer Science Faculty Publications

In this paper we present work on a project funded by the National Science Foundation with a goal of unifying the Artificial Intelligence (AI) course around the theme of machine learning. Our work involves the development and testing of an adaptable framework for the presentation of core AI topics that emphasizes the relationship between AI and computer science. Several hands-on laboratory projects that can be closely integrated into an introductory AI course have been developed. We present an overview of one of the projects and describe the associated curricular materials that have been developed. The project uses machine learning as …

Min–Max Hyperellipsoidal Clustering For Anomaly Detection In Network Security, Suseela T. Sarasamma, Qiuming Zhu

Computer Science Faculty Publications

A novel hyperellipsoidal clustering technique is presented for an intrusion-detection system in network security. Hyperellipsoidal clusters toward maximum intracluster similarity and minimum intercluster similarity are generated from training data sets. The novelty of the technique lies in the fact that the parameters needed to construct higher order data models in general multivariate Gaussian functions are incrementally derived from the data sets using accretive processes. The technique is implemented in a feedforward neural network that uses a Gaussian radial basis function as the model generator. An evaluation based on the inclusiveness and exclusiveness of samples with respect to specific criteria is …

Effective Teaching Of Programming Concepts Using Low-Resolution (Character) Graphics, Tamisra Haran Sanyal

Computer Science Faculty Publications

For novice students of Computer Programming, the difference between Floating point numbers and Integers (and consequent difference between arithmetic operations on them) appears to be a difficult concept to grasp. In popular languages such as C++ or Java, this difficulty is made more acute by the fact that the same symbol is used for both floating point division and integer division.1 Without a proper grasp of the difference between these two fundamentally different kinds of numbers, students would also find it difficult to understand that floating point results should not be compared for equality. I was therefore interested in finding …

Interacting With Web Hierarchies, Saverio Perugini, Naren Ramakrishnan

Computer Science Faculty Publications

Web site interfaces are a particularly good fit for hierarchies in the broadest sense of that idea, i.e. a classification with multiple attributes, not necessarily a tree structure. Several adaptive interface designs are emerging that support flexible navigation orders, exposing and exploring dependencies, and procedural information-seeking tasks. This paper provides a context and vocabulary for thinking about hierarchical Web sites and their design. The paper identifies three features that interface to information hierarchies. These are flexible navigation orders, the ability to expose and explore dependencies, and support for procedural tasks. A few examples of these features are also provided

An Approach To The Optimization Of Convergent Networks On Ip/Mpls With An Optical Gmpls Backbone In Multicast, Yezid Donoso, Carolina Alvarado, Alfredo J. Perez, Ivan Herazo

Computer Science Faculty Publications

This paper shows the solution of a multiobjective scheme for multicast transmissions in MPLS networks with a GMLS optical backbone using evolutive algorithms. It has not been showed models that optimize one or more parameters integrating these two types of networks. Because the proposed scheme is a NP-Hard problem, an algorithm has been developed to solve the problem on polynomial time. The main contributions of this paper are the proposed mathematical model and the algorithm to solve it.

Answer Set Programming Based On Propositional Satisfiability, Enrico Giunchiglia, Yuliya Lierler, Marco Maratea

Computer Science Faculty Publications

Answer set programming (ASP) emerged in the late 1990s as a new logic programming paradigm that has been successfully applied in various application domains. Also motivated by the availability of efficient solvers for propositional satisfiability (SAT), various reductions from logic programs to SAT were introduced. All these reductions, however, are limited to a subclass of logic programs or introduce new variables or may produce exponentially bigger propositional formulas. In this paper, we present a SAT-based procedure, called ASPSAT, that (1) deals with any (nondisjunctive) logic program, (2) works on a propositional formula without additional variables (except for those possibly introduced …