12973395
Colimits for Concurrent Collectors
This case study applies techniques of formal program development by specification refinement and composition to the problem of concurrent garbage collection. The specification formalism is mainly based on declarative programming paradigms, the imperative aspect is dealt with by using monads. We also sketch the use of temporal logic in connection with monadic specifications.
44957593
Toward a Classification Approach to Design
This paper addresses the problem of how to construct refinements of specifications formally and incrementally. The key idea is to use a taxonomy of abstract design concepts, each represented by a design theory An abstract design concept is applied by constructing a specification morphism from its design theory to a requirement specification. Procedures for propagating constraints, computing colimits, and constructing specification morphisms provide computational support for this approach. Although we conjecture that classification generally applies to the incremental application of knowledge represented in a taxonomy of design theories, this paper mainly focuses on algorithm design theories and presents several examples of design by classification.
12681881
Synthesis of Constraint Algorithms
7947888
Constructing Specification Morphisms
Specification morphisms underlie the refinement of algebraic specifications and provide the logical foundations for algorithm and data structure design. We present four techniques for formally, even mechanically, constructing specification morphisms. The first two techniques, verifying a manually constructed signature morphism and composition of specification morphisms are well-known. The remaining two techniques exploit the axioms of the source specification to help infer the translation of sort and function symbols from the source specification. The third, unskolemization, finds the translation of a function symbol by replacing occurrences of it in an axiom by an existentially quantified variable. A constructive proof of the translated axiom yields a witness to the existential that serves as the desired translation of the function symbol. The fourth technique, connections between specifications, allows the transfer of structure from one specification morphism to another. The unskolemization and connection techniques arose as abstractions from the algorithm design tactics implemented in the KIDS program transformation system (Smith (1990)). They suggest a more general approach to providing mechanized support for applying design knowledge expressed axiomatically.
17878068
Guarded Transitions in Evolving Specifications
We represent state machines in the category of specifications, where assignment statements correspond exactly to interpretations between theories [7, 8]. However, the guards on an assignment require a special construction. In this paper we raise guards to the same level as assignments by treating each as a distinct category over a shared set of objects. A guarded assignment is represented as a pair of arrows, a guard arrow and an assignment arrow. We give a general construction for combining arrows over a factorization system, and show its specialization to the category of specifications. This construction allows us to define the fine structure of state machine morphisms with respect to guards. Guards define the flow of control in a computation, and how they may be translated under refinement is central to the formal treatment of safety, liveness, concurrency, and determinism.
206511487
Composition and refinement of behavioral specifications
This paper presents a mechanizable framework for specifying, developing, and reasoning about complex systems. The framework combines features from algebraic specifications, abstract state machines, and refinement calculus, all couched in a categorical setting. In particular, we show how to extend algebraic specifications to evolving specifications (especs) in such a way that composition and refinement operations extend to capture the dynamics of evolving, adaptive, and self-adaptive software development, while remaining efficiently computable. The framework is partially implemented in the Epoxi system.
27096788
Mobile Location
7569023
Journey planning based on user needs
In this paper we discuss potential developments to the design of pre-trip in-home journey planning services, to include support for additional user needs. These needs were identified through stakeholder interviews as contributing to actual decisions in route selection scenarios and include: safety, weather and even fitness. A journey planner was designed to allow users to articulate these constraints and a series of paper prototypes were evaluated through cognitive walkthroughs. An exploratory study compared three designs and provided rationale for the most effective interaction method, informing an implementation plan.
1432381
Detecting and Browsing Events in Unstructured text
Previews and overviews of large, heterogeneous information resources help users comprehend the scope of collections and focus on particular subsets of interest. For narrative documents, questions of "what happened? where? and when?" are natural points of entry. Building on our earlier work at the Perseus Project with detecting terms, place names, and dates, we have exploited co-occurrences of dates and place names to detect and describe likely events in document collections. We compare statistical measures for determining the relative significance of various events. We have built interfaces that help users preview likely regions of interest for a given range of space and time by plotting the distribution and relevance of various collocations. Users can also control the amount of collocation information in each view. Once particular collocations are selected, the system can identify key phrases associated with each possible event to organize browsing of the documents themselves.
2029665
Minimum Risk Annealing for Training Log-Linear Models
When training the parameters for a natural language system, one would prefer to minimize 1-best loss (error) on an evaluation set. Since the error surface for many natural language problems is piecewise constant and riddled with local minima, many systems instead optimize log-likelihood, which is conveniently differentiable and convex. We propose training instead to minimize the expected loss, or risk. We define this expectation using a probability distribution over hypotheses that we gradually sharpen (anneal) to focus on the 1-best hypothesis. Besides the linear loss functions used in previous work, we also describe techniques for optimizing nonlinear functions such as precision or the BLEU metric. We present experiments training log-linear combinations of models for dependency parsing and for machine translation. In machine translation, annealed minimum risk training achieves significant improvements in BLEU over standard minimum error training. We also show improvements in labeled dependency parsing.
30879884
Generation of lower bounds for minimum span frequency assignment
Minimum span frequency assignment problems require lower bounds for the span in order to assess the quality of individual assignments, and to effectively compare different meta-heuristic algorithms. The generation of good lower bounds requires the identification of critical subproblems. These subproblems are subgraphs of a constraint graph. Sometimes clique subgraphs lead to good lower bounds. However for some problems the clique must be modified in order to obtain the best possible bound. This can be time consuming, requires manual intervention and is dependent on the initial clique obtained and the specific problem. For practical use, a simple bounding technique is needed that can be universally applied to all problems without modification. Two algorithms based on meta-heuristics are presented that aim to find a subproblem that gives the best possible lower bound. This avoids the need for clique detection routines and manual intervention, and gives a robust and automatic method for generating lower bounds for all minimum span problems. These algorithms use mathematical programming formulations of the frequency assignment problem. Extensive testing on a wide range of problems shows that bounds from the new algorithms match those using previous techniques, and in some cases are significantly better.