Computer Sciences Commons^™

A Pattern Language For Extensible Program Representation, Andrew P. Black, Daniel Vainsencher

Computer Science Faculty Publications and Presentations

For the last 15 years, implementors of multiple view programming environments have sought a single code model that would form a suitable basis for all of the program analyses and tools that might be applied to the code. They have been unsuccessful. The consequences are a tendency to build monolithic, single-purpose tools, each of which implements its own specialized analyses and optimized representation. This restricts the availability of the analyses, and also limits the reusability of the representation by other tools. Unintegrated tools also produce inconsistent views, which reduce the value of multiple views. This article describes a set of …

India’S Rise As A Software Power: Governmental Policy Factors, Tad Drozdowski, Hai Huynh, Brian Lininger, Yicheng Peng, Naruedom Sakulyong

Engineering and Technology Management Student Projects

The Indian government’s policies toward an open, global market, support of educational institutions, and enhancement of appropriate infrastructure helped enable their software industry to become critical components of India’s economic growth in the 1990s. The Technical, Organizational, and Personal perspective (T, O, and P) model is utilized to examine different affects that each perspective, inclusive of government policies, has on a socio-technical system (Software development in India). The Indian government has provided substantial economic liberalization to support their software industries, though continued reform is necessary to ensure that they remain a software superpower.

A Short Tutorial On Reconstructability Analysis, Martin Zwick

Complex Systems Faculty Publications and Presentations

This talk will present the basic ideas of Reconstructability Analysis. RA is a general modeling methodology developed in the systems community since the early 60s (pioneered by Ross Ashby) for exploratory (data mining, machine learning) and confirmatory modeling. RA is based in graph theory, set theory, information theory, and statistics. It is applicable to qualitative (nominal) and, via binning, to quantitative (continuous) data, with both statistical & non-statistical applications. It overlaps and augments more widely known methods, e.g., log-linear modeling and Bayesian networks.

Keywords: Reconstructability Analysis, Log-Linear Modeling, categorical data, multivariate statistics, exploratory modeling, confirmatory modeling

Unifying Reciprocal Altruism And Inclusive Fitness Theories Of Altruism, Jeffrey Fletcher, Martin Zwick

Complex Systems Faculty Publications and Presentations

In lieu of an abstract, here is the outline:

Background

• Some History
• IPD Model of Reciprocal Altruism
• Problems Applying Hamilton’s Rule (HR)

Unification: Applying HR to Reciprocal Altruism

• Queller’s Generalized HR
• Conditional Behaviour and Non-Additivity
• Symbiotic Mutualisms

Implications of Unification

• Progressive Generalization of HR
• What happened to “indirect” fitness?
• Conceptual Parsimony

Binary Decision Diagrams And Crisp Possibilistic Reconstructability Analysis, Martin Zwick, Alan Mishchenko

Complex Systems Faculty Publications and Presentations

The paper discusses the application of Binary Decision Diagrams (BDDs) in the reconstructability analysis of crisp possibilistic systems. In particular, we show how BDDs can be used to represent set-theoretic relations and implement the three basic operations of reconstructability analysis.

What's Wrong With Inclusive Fitness?, Jeffrey Fletcher, Martin Zwick, Michael Doebeli, David Sloan Wilson

Complex Systems Faculty Publications and Presentations

In lieu of an abstract, here is the first paragraph:

In a recent issue of TREE, Foster et al. [1] defend inclusive fitness theory [2] from recent challenges [3,4]. The main author of these challenges, E.O. Wilson, argues that inclusive fitness (also called kin selection [5]) may not be the main explanation for the evolution of altruism and eusociality. In contrast, Foster et al. claim that inclusive fitness is not only the most prominent explanation for altruism, but that genetic “relatedness is always required for altruism to evolve” [1, p. 59]. Here we take issue with their claim about …

Addressing Cheating And Workload Characterization In Online Games, Christopher Chambers

Dissertations and Theses

The Internet has enabled the popular pastime of playing video games to grow rapidly by connecting game players in disparate locations. However, with popularity have come the two challenges of hosting a large number of users and detecting cheating among users. For reasons of control, security, and ease of development, the most popular system for hosting on-line games is the client server architecture. This is also the most expensive and least scalable architecture for the game publisher, which drives hosting costs upwards with the success of the game. In addition to the expense of hosting, as a particular game grows …

Reconstructability Analysis As A Tool For Identifying Gene-Gene Interactions In Studies Of Human Diseases: Ieee Version, Martin Zwick, Stephen Shervais, Patricia Kramer

Complex Systems Faculty Publications and Presentations

There are a number of human diseases that are caused by the epistatic interaction of multiple genes. Detecting these interactions with standard statistical tools is difficult, because there may be an interaction effect, but minimal or no main effect. Reconstructability analysis uses Shannon’s information theory to detect relationships between variables in categorical datasets. We apply reconstructability analysis to data generated by five different models of gene-gene interaction, with heritability levels from 0.053 to 0.008, using 200 controls and 200 cases. We find that even with heritability levels as low as 0.008, and with the inclusion of 50 non-associated genes in …

Can Infopipes Facilitate Reuse In A Traffic Application?, Emerson Murphy-Hill, Chuan-Kai Lin, Andrew P. Black, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Infopipes are presented as reusable building blocks for streaming applications. To evaluate this claim, we have built a significant traffic application in Smalltalk using Infopipes. This poster presents a traffic problem and solution, a short introduction to Infopipes, and the types of reuse Infopipes facilitate in our implementation.

Application Of Information-Theoretic Data Mining Techniques In A National Ambulatory Practice Outcomes Research Network, Adam Wright, Thomas N. Ricciardi, Martin Zwick

Complex Systems Faculty Publications and Presentations

The Medical Quality Improvement Consortium data warehouse contains de-identified data on more than 3.6 million patients including their problem lists, test results, procedures and medication lists. This study uses reconstructability analysis, an information-theoretic data mining technique, on the MQIC data warehouse to empirically identify risk factors for various complications of diabetes including myocardial infarction and microalbuminuria. The risk factors identified match those risk factors identified in the literature, demonstrating the utility of the MQIC data warehouse for outcomes research, and RA as a technique for mining clinical data warehouses.

Reconstructability Analysis And Log-Linear Modeling, Martin Zwick

Complex Systems Faculty Publications and Presentations

Reconstructability Analysis (RA) is a method developed within the systems community for analyzing nominal (or discretized) data. RA both overlaps and extends Log-Linear (LL) modeling, and the purpose of this talk is to introduce RA to researchers unfamiliar with it. Two aspects of RA will be focused on: (1) its use for exploratory, as opposed to confirmatory, modeling – searching for good models in a vast space of possible models, and (2) state-based RA – analyzing data not in terms of relations among variables but in terms of relations among specific states of variables. Examples of applications to social science …

Rcu Semantics: A First Attempt, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

There is not yet a formal statement of RCU (read-copy update) semantics. While this lack has thus far not been an impediment to adoption and use of RCU, it is quite possible that formal semantics would point the way towards tools that automatically validate uses of RCU or that permit RCU algorithms to be automatically generated by a parallel compiler. This paper is a first attempt to supply a formal definition of RCU. Or at least a semi-formal definition: although RCU does not yet wear a tux (though it does run in Linux), at least it might yet wear some …

Locality, Network Control And Anomaly Detection, Jim Binkley

Computer Science Faculty Publications and Presentations

Ourmon is a near real-time network monitoring and anomaly detection system that captures packets using port-mirroring on Ethernet switches. It primarily displays data via web graphics using either RRDTOOL stripcharts or via histograms for top talker style graphs. We have developed a theory that network scanning launched primarily by worm programs including TCP and UDP scanners may be caught by monitoring network control data including TCP control packets (SYNS, FINS, RESETS) and ICMP errors, or by monitoring certain carefully chosen metadata such as the flow count itself. In this paper we concentrate on TCP and present a ”flow tuple” focused …

Dynamic Systems And Organizational Decision-Making Processes In Nonprofits, Jennifer S. Tucker, Jennifer C. Cullen, Robert S. Sinclair, Wayne Wakeland

Complex Systems Faculty Publications and Presentations

Social purpose organizations (SPOs) are nonprofit organizations that fulfill their social missions by seeking revenue from traditional business activities. SPOs often face difficulties attracting and retaining organizational members with the necessary mix of social and business skills and values. When coupled with resource limitations and an unstable environment, these issues create serious strategic challenges for leaders of small SPOs. In the present article, the authors describe several systems thinking concepts that may enable leaders to understand and therefore more effectively contend with the challenges of the SPO context. The authors also present a case study demonstrating the utility of systems …

Hamilton's Rule In Reciprocal Altruism And Symbiosis, Jeffrey Fletcher, Martin Zwick

Complex Systems Faculty Publications and Presentations

In lieu of an abstract, here is the outline:

Do Inclusive Fitness and Reciprocal Altruism Models embody different or similar mechanisms?

Background

• The Prisoner’s Dilemma (PD), Hamilton’s Rule (Queller’s version)

Apply Hamilton’s Rule to Reciprocal Altruism:

• Iterated Prisoner’s Dilemma model
• A model of symbiosis

Towards a Unified Theory

Combining Optimizer And Metamodeling For Railcar Structural Optimization, Longjun Liu, Wayne Wakeland

Complex Systems Faculty Publications and Presentations

Stress constraint is a hard issue for structural topology optimization, especially for large-scale structures, e.g. railcars. Another technique is proposed to combine a sizing optimizer with metamodelling for topology optimization. At the lower level, for each topology design sampled within the topology design space, a sizing optimizer finds feasible and optimal solutions in terms of sizing variables (plate thickness in continuum structures). All performance constraints such as stress, displacement, and stability, are handled only at this level. At the upper level, a metamodel is built to fit all the optimal solutions found at the lower level and is optimized for …

Heuristic Optimization As A V&V Tool For Software Process Simulationmodels, Wayne Wakeland, Stephen Shervais, David Raffo

Complex Systems Faculty Publications and Presentations

This work illustrates the use of heuristic algorithms to improve the verification and validation of software process simulation models. To use this approach, an optimization problem is formulated to guide a heuristic search algorithm that will attempt to locate particular combinations of parameter values that yield surprising results. These surprising results often help the modeler to identify flaws in the model logic that would otherwise remain undetected. The general concepts are discussed and a simple example is provided.

Enhancements To Crisp Possibilistic Reconstructability Analysis, Anas Al-Rabadi, Martin Zwick

Complex Systems Faculty Publications and Presentations

Modified Reconstructibility Analysis (MRA), a novel decomposition within the framework of set-theoretic (crisp possibilistic) Reconstructibility Analysis, is presented. It is shown that in some cases while 3-variable NPN-classified Boolean functions are not decomposable using Conventional Reconstructibility Analysis (CRA), they are decomposable using Modified Reconstructibility Analysis (MRA). Also, it is shown that whenever a decomposition of 3-variable NPN-classified Boolean functions exists in both MRA and CRA, MRA yields simpler or equal complexity decompositions. A comparison of the corresponding complexities for Ashenhurst-Curtis decompositions, and Modified Reconstructibility Analysis (MRA) is also presented. While both AC and MRA decompose some but …

Teabag: A Debugger For Curry, Stephen Lee Johnson

Dissertations and Theses

This thesis describes TeaBag, which is a debugger for functional logic computations. TeaBag is an accessory of a virtual machine currently under development. A distinctive feature of this machine is its operational completeness of computations, which places novel demands on a debugger. This thesis describes the features of TeaBag, in particular the handling of non-determinism, the ability to control nondeterministic steps, to remove context information, to toggle eager evaluation, and to set breakpoints on both functions and terms. This thesis also describes TeaBag's architecture and its interaction with the associated virtual machine. Finally, some debugging sessions of defective programs are …

Toward A Sound Integration Of Isabelle With A Combined Decision Procedure, Tom Harke

Computer Science Faculty Publications and Presentations

I present work on a project to integrate Isabelle, an extremely versatile interactive proof assistant, with a combined decision procedure, the Cooperating Validity Checker (CVC). Isabelle is sound and flexible, however it is often tedious to use. CVC is fully automatic, but only handles decision problems expressible over a relatively weak set of theories including linear arithmetic, uninterpreted functions, data types, and firstorder quantifier-free logic. My goal is to increase the amount of automation in Isabelle, by making it use CVC as an oracle for such problems, but without compromising Isabelle’s soundness.

In this paper I report on the progress …

Reconstructability Analysis With Fourier Transforms, Martin Zwick

Complex Systems Faculty Publications and Presentations

Fourier methods used in two‐ and three‐dimensional image reconstruction can be used also in reconstructability analysis (RA). These methods maximize a variance‐type measure instead of information‐theoretic uncertainty, but the two measures are roughly collinear and the Fourier approach yields results close to that of standard RA. The Fourier method, however, does not require iterative calculations for models with loops. Moreover, the error in Fourier RA models can be assessed without actually generating the full probability distributions of the models; calculations scale with the size of the data rather than the state space. State‐based modeling using the Fourier approach is also …

Using Design Of Experiments, Sensitivity Analysis, And Hybrid Simulation To Evaluate Changes To A Software Development Process: A Case Study, Wayne Wakeland, Robert H. Martin, David Raffo

Complex Systems Faculty Publications and Presentations

Hybrid simulation models combine the high-level project issues of System Dynamics models along with the detailed process representation of discrete event simulation models. Hybrid models not only capture the best of both of these simulation paradigms, but they also are able to address new issues that are important in managing complex real-world development projects that neither the System Dynamics nor Discrete Event simulation paradigms are able to address alone.

In order to reap the full benefits from a simulation model, a structured approach for analyzing model results is necessary. The recommended approach is a combination of the Design of Experiments …

Directed Extended Dependency Analysis For Data Mining, Thaddeus T. Shannon, Martin Zwick

Complex Systems Faculty Publications and Presentations

Extended dependency analysis (EDA) is a heuristic search technique for finding significant relationships between nominal variables in large data sets. The directed version of EDA searches for maximally predictive sets of independent variables with respect to a target dependent variable. The original implementation of EDA was an extension of reconstructability analysis. Our new implementation adds a variety of statistical significance tests at each decision point that allow the user to tailor the algorithm to a particular objective. It also utilizes data structures appropriate for the sparse data sets customary in contemporary data mining problems. Two examples that illustrate different approaches …

A Comparison Of Modified Reconstructability Analysis And Ashenhurst‐Curtis Decomposition Of Boolean Functions, Anas Al-Rabadi, Marek Perkowski, Martin Zwick

Complex Systems Faculty Publications and Presentations

Modified reconstructability analysis (MRA), a novel decomposition technique within the framework of set‐theoretic (crisp possibilistic) reconstructability analysis, is applied to three‐variable NPN‐classified Boolean functions. MRA is superior to conventional reconstructability analysis, i.e. it decomposes more NPN functions. MRA is compared to Ashenhurst‐Curtis (AC) decomposition using two different complexity measures: log‐functionality, a measure suitable for machine learning, and the count of the total number of two‐input gates, a measure suitable for circuit design. MRA is superior to AC using the first of these measures, and is comparable to, but different from AC, using the second.

State-Based Reconstructability Analysis, Martin Zwick, Michael S. Johnson

Complex Systems Faculty Publications and Presentations

Reconstructability analysis (RA) is a method for detecting and analyzing the structure of multivariate categorical data. While Jones and his colleagues extended the original variable‐based formulation of RA to encompass models defined in terms of system states, their focus was the analysis and approximation of real‐valued functions. In this paper, we separate two ideas that Jones had merged together: the “g to k” transformation and state‐based modeling. We relate the idea of state‐based modeling to established variable‐based RA concepts and methods, including structure lattices, search strategies, metrics of model quality, and the statistical evaluation of model fit for analyses based …

An Overview Of Reconstructability Analysis, Martin Zwick

Complex Systems Faculty Publications and Presentations

This paper is an overview of reconstructability analysis (RA), a discrete multivariate modeling methodology developed in the systems literature; an earlier version of this tutorial is Zwick (2001). RA was derived from Ashby (1964), and was developed by Broekstra, Cavallo, Cellier Conant, Jones, Klir, Krippendorff, and others (Klir, 1986, 1996). RA resembles and partially overlaps log‐line (LL) statistical methods used in the social sciences (Bishop et al., 1978; Knoke and Burke, 1980). RA also resembles and overlaps methods used in logic design and machine learning (LDL) in electrical and computer engineering (e.g. Perkowski et al., 1997). Applications of RA, like …

Reversible Modified Reconstructability Analysis Of Boolean Circuits And Its Quantum Computation, Anas Al-Rabadi, Martin Zwick

Complex Systems Faculty Publications and Presentations

Modified Reconstructability Analysis (MRA) can be realized reversibly by utilizing Boolean reversible (3,3) logic gates that are universal in two arguments. The quantum computation of the reversible MRA circuits is also introduced. The reversible MRA transformations are given a quantum form by using the normal matrix representation of such gates. The MRA-based quantum decomposition may play an important role in the synthesis of logic structures using future technologies that consume less power and occupy less space.

Modified Reconstructability Analysis For Many-Valued Functions And Relations, Anas Al-Rabadi, Martin Zwick

Complex Systems Faculty Publications and Presentations

A novel many-valued decomposition within the framework of lossless Reconstructability Analysis is presented. In previous work, Modified Recontructability Analysis (MRA) was applied to Boolean functions, where it was shown that most Boolean functions not decomposable using conventional Reconstructability Analysis (CRA) are decomposable using MRA. Also, it was previously shown that whenever decomposition exists in both MRA and CRA, MRA yields simpler or equal complexity decompositions. In this paper, MRA is extended to many-valued logic functions, and logic structures that correspond to such decomposition are developed. It is shown that many-valued MRA can decompose many-valued functions when CRA fails to do …

Reconstructability Analysis Detection Of Optimal Gene Order In Genetic Algorithms, Martin Zwick, Stephen Shervais

Complex Systems Faculty Publications and Presentations

The building block hypothesis implies that genetic algorithm efficiency will be improved if sets of genes that improve fitness through epistatic interaction are near to one another on the chromosome. We demonstrate this effect with a simple problem, and show that information-theoretic reconstructability analysis can be used to decide on optimal gene ordering.

Reconstructability Analysis: Theory And Applications [Editorial Introduction], Martin Zwick, Guangfu Shu, Yi Lin

Complex Systems Faculty Publications and Presentations

Reconstructability analysis (RA) dates back to the pioneering work of Ashby in the mid-1960s. In the 1970s and 1980s, RA was the subject of very active research in the systems community. It receded for a time as a focus of activity, but the special issue of the International Journal of General Systems in 1996 on the General Systems Problem Solver and the special IJGS issue in 2000 on Reconstructability Analysis in China marked the renewal of interest in this area. The current volume is part of this resurgence of activity. It collects together papers from the group at Portland State …