It is known that, when normalized by$n$as$n \rightarrow \infty$, the expected length of a longest common subsequence of$d$random strings of length$n$over an alphabet of size$\sigma$converges to a constant that depends only on$d$and$\sigma$. These values are known as the Chvátal-Sankoff constants, and determining their exact values is a major open problem. Building on previous algorithms for lower-bounding the constants, we implement parallelization, introduce significant runtime optimizations, and design an efficient recursive memory reading and writing scheme. With this, we obtain a new best lower bound of 0.792665992 for$\sigma=2, d=2$. We additionally improve upon almost all previously reported lower bounds for the Chvátal-Sankoff constants when either the size of alphabet, the number of strings, or both are larger than 2.

Software evolution is an essential challenge for all software engineers, typically addressed solely using code versioning systems and language-specific code analysis tools. Most versioning systems view the evolution of a system as a directed acyclic graph of steps, with independent branches that could be merged. What these systems fail to provide is the ability to ensure stable APIs or that each subsequent evolution represents a cohesive extension yielding a valid system. Modular software evolution ensures that APIs remain stable, which is achieved by ensuring that only additional methods, fields, and data types are added, while treating existing modules through blackbox interfaces. Even with these restrictions, it must be possible to add new variations, fields, and methods without extensive duplication of prior module code. In contrast to most literature, our focus is on ensuring modular software evolution using mainstream object-oriented programming languages, instead of resorting to novel language extensions. We present a novel CoCo design pattern that supports type-safe covariantly overridden convert methods to transform earlier data type instances into their newest evolutionary representation to access operations that had been added later. CoCo supports both binary methods and producer methods. We validate and contrast our approach using a well-known compiler construction case study that other researchers have also investigated for modular evolution. Our resulting implementation relies on less boilerplate code, is completely type-safe, and allows clients to use normal object-oriented calling conventions. We also compare CoCo with existing approaches to the Expression Problem. We conclude by discussing how CoCo could change the direction of currently proposed Java language extensions to support closed-world assumptions about data types, as borrowed from functional programming.

The composition of features that interact with each other is challenging. Algebraic formalisms have been proposed by various authors to describe feature compositions and their interactions. The intention of feature compositions is the composition of fragments of documents of any kind to a product that fulfills users' requirements expressed by a feature selection. These modules often include code modules of typed programming languages whereas the proposed algebraic formalism is agnostic to types. This situation can lead to product code which is not type correct. In addition, types can carry semantic information on a program or module. We present a type system and connect it to an algebraic formalism thereby allowing automatic synthesis of feature compositions yielding well-typed programs.

For many software engineers, object-oriented frameworks represent the highest level of achievement in extensible design. The framework designers become experts in a specific application domain and design cooperating classes that impose specific responsibilities and collaborations for those seeking to extend the framework. In short, once a framework matures, it has complicated usage patterns that must be followed otherwise nothing works. Turning a framework into a software product line is challenging because of the difficulty in coding these complex behaviors and enabling the configuration of product line members using the framework. We propose to support this migration process by showing how to design a repository of modular units to synthesize member applications compositionally. These units are formalized using combinatory logic synthesis, a type-based approach to component-oriented synthesis. We demonstrate the feasibility of our approach with a Java-based product line for which we can automatically synthesize member applications.

Developing a Software Product Line is a significant investment since domain experts must work together with software developers to understand and model a specific domain and then transform those models into a working software system. A product line increases the essential complexity of software assets because of the widespread variability among the member applications and the requirement to configure an application by its desired features. We seek mechanisms and theories to reduce the manual effort in writing the software. This workshop focuses on a broad range of approaches that increase the amount of synthesized code in both the shared code assets of the product line as well as individual member applications. We are especially interested in modular approaches that provide a theory of composition for assembling together modular units (such as classes, mixins, combinators, aspects, and modules).

Dynamic plan migration is concerned with the on-the-fly transition from one continuous query plan to a semantically equivalent yet more efficient plan. Migration is important for stream monitoring systems where long-running queries may have to withstand fluctuations in stream workloads and data characteristics. Existing migration methods generally adopt a pause-drain-resume strategy that pauses the processing of new data, purges all old data in the existing plan, until finally the new plan can be plugged into the system. However, these existing strategies do not address the problem of migrating query plans that contain stateful operators, such as joins. We now develop solutions for online plan migration for continuous stateful plans. In particular, in this paper, we propose two alternative strategies, called the moving state strategy and the parallel track strategy, one exploiting reusability and the second employs parallelism to seamlessly migrate between continuous join plans without affecting the results of the query. We develop cost models for both migration strategies to analytically compare them. We embed these migration strategies into the CAPE [7], a prototype system of a stream query engine, and conduct a comparative experimental study to evaluate these two strategies for window-based join plans. Our experimental results illustrate that the two strategies can vary significantly in terms of output rates and intermediate storage spaces given distinct system configurations and stream workloads.

There is a constant need for practical, efficient and cost-effective software evolution techniques. We propose a novel evolution methodology that integrates the concepts of features, regression tests, and component-based software engineering (CBSE). Regression test cases are untapped resources, full of information about system features. By exercising each feature with their associated test cases using code profilers and similar tools, code can be located and refactored to create components. These components are then inserted back into the legacy system, ensuring a working system structure. This methodology is divided into three parts. Part one identifies the source code associated with features that need evolution. Part two deals with creating components and part three measures results. By applying this methodology, AFS has successfully restructured its enterprise legacy system and reduced the costs of future maintenance. Additionally, the components that were refactored from the legacy system are currently being used within a web-enabled application.

Software component consumers are entitled to trusted components. This panel addresses the criteria for trusted components and presents generally accepted definitions for all terms used to describe both software components and the methods and processes required to verify trusted software components.

The purpose of this paper is to gain experience in solving real problems faced by a company. We first specify the system architecture of the AFS Master System (R) using our Component Specification Language (CSL). We then identified various problem evident in the current architecture of the AFS Master System (R). Based on an analysis of the architecture and these problems, we proposed a modification to the software architecture that addressed out of the seven main problems identified. The engineers made the appropriate changes to the software system (about one week of effort) and have noted a 25% improvement in efficiency as well as an improved system organization that can be more easily changed to meet future demands. We believe the type of architectural change described in this paper will prove useful to developers using similar technologies as described in this paper.

The widespread construction of software systems from pre-existing, independently developed software components will only occur when application builders can adapt software components to suit their needs. We propose that software components provide two interfaces-one for behavior and one for adapting that behavior as needed. The ADAPT framework presented in the paper supports both component designers in creating components that can easily be adapted, and application builders in adapting software components. The motivating example, using Java-Beans, shows how adaptation, not customization, is the key to component based software.

Database management systems (DBMSs) have been increasingly used for advanced application domains, such as software development environments, workflow management systems, computer-aided design and manufacturing, and managed healthcare. In these domains, the standard correctness model of serializability is often too restrictive. The authors introduce the notion of a concurrency control language (CCL) that allows a database application designer to specify concurrency control policies to tailor the behavior of a transaction manager. A well-crafted set of policies defines an extended transaction model. The necessary semantic information required by the CCL run-time engine is extracted from a task manager, a (logical) module by definition included in all advanced applications. This module stores task models that encode the semantic information about the transactions submitted to the DBMS. They have designed a rule-based CCL, called CORD, and have implemented a run-time engine that can be hooked to a conventional transaction manager to implement the sophisticated concurrency control required by advanced database applications. They present an architecture for systems based on CORD and describe how they integrated the CORD engine with the Exodus Storage Manager to implement altruistic locking.

Layered and componentized systems promise substantial benefits from dividing responsibilities, but it is still unresolved how to construct a system from pre-ezisting, independently developed pieces.Good solutions to this problem, in general or for specific classes of components, should reduce duplicate implementation efforts and promote reuse of large scale subsystems.We tackle the domain of software development environments and present an architecture for retrofitting external concurrency control components onto existing environment frameworks.We describe a sample ECC component, explain how we added concurrency control to a commercial product that had none, and briefly sketch how we replaced the concurrency control mechanism of a research system.

Reengineering a large code base can be a monumental task, and the situation becomes even worse if the code is concomitantly being modified. Since January 1992, we have been using the MARVEL process centered environment (PCE) for all of our software development, and are currently using it to develop the Oz PCE (MARVEL's successor). Towards this effort, we are reengineering Oz's code base to isolate the process engine, transaction manager, and object management system as separate components that can be used in arbitrary systems. In this paper, we show how a PCE can assist teams of users in carrying out code reengineering while allowing them to continue their normal code development. The key features to this approach are its incremental nature and the ability of the PCE to automate most of the tasks necessary to maintain the consistency of the code base.>