New mechanisms for invocation handling in concurrent programming languages

Invocation handling mechanism in many concurrent languages have significant limitations that make it difficult or costly to solve common programming situations encountered in program visualization, debugging, and scheduling scenarios. This paper discusses these limitations, introduces new language mechanisms aimed at remedying these limitations, and presents an implementation of the new mechanisms. The examples are given in SR; the new mechanisms and implementation are an extension of SR and its implementation. However, these new mechanisms are applicable to other concurrent languages. They can augment or replace current invocation handling mechanisms.     

Evolving BlenX programs to simulate the evolution of biological networks

We present a formal approach to study the evolution of biological networks. We use the Beta Workbench and its BlenX language to model and simulate networks in connection with evolutionary algorithms. Mutations are done on the structure of BlenX programs and networks are selected at any generation by using a fitness function. The feasibility of the approach is illustrated with a simple example.     

GAP: A graphical environment for matrix visualization and cluster analysis

GAP is a Java-designed exploratory data analysis (EDA) software for matrix visualization (MV) and clustering of high-dimensional data sets. It provides direct visual perception for exploring structures of a given data matrix and its corresponding proximity matrices, for variables and subjects. Various matrix permutation algorithms and clustering methods with validation indices are implemented for extracting embedded information. GAP has a friendly graphical user interface for easy handling of data and proximity matrices. It is more powerful and effective than conventional graphical methods when dimension reduction techniques fail or when data is of ordinal, binary, and nominal type.     

Fitting finite mixtures of generalized linear regressions in R

R package flexmix provides flexible modelling of finite mixtures of regression models using the EM algorithm. Several new features of the software such as fixed and nested varying effects for mixtures of generalized linear models and multinomial regression for a priori probabilities given concomitant variables are introduced. The use of the software in addition to model selection is demonstrated on a logistic regression example.     

Range and Roots: Two common patterns for specifying and propagating counting and occurrence constraints

We propose Range and Roots which are two common patterns useful for specifying a wide range of counting and occurrence constraints. We design specialised propagation algorithms for these two patterns. Counting and occurrence constraints specified using these patterns thus directly inherit a propagation algorithm. To illustrate the capabilities of the Range and Roots constraints, we specify a number of global constraints taken from the literature. Preliminary experiments demonstrate that propagating counting and occurrence constraints using these two patterns leads to a small loss in performance when compared to specialised global constraints and is competitive with alternative decompositions using elementary constraints.     

Weighted comparison of two cumulative incidence functions with R-CIFsmry package

In this paper we propose a class of flexible weight functions for use in comparison of two cumulative incidence functions. The proposed weights allow the users to focus their comparison on an early or a late time period post treatment or to treat all time points with equal emphasis. These weight functions can be used to compare two cumulative incidence functions via their risk difference, their relative risk, or their odds ratio. The proposed method has been implemented in the R-CIFsmry package which is readily available for download and is easy to use as illustrated in the example.     

Kanga(ROO): Handling the micro-DST of the BaBar experiment with ROOT

A system based on ROOT for handling the micro-DST of the BaBar experiment is described. The purpose of the Kanga system is to have micro-DST data available in a format well suited for data distribution within a world-wide collaboration with many small sites. The design requirements, implementation and experience in practice after three years of data taking by the BaBar experiment are presented.     

PVS#: Streamlined Tacticals for PVS

The semantics of a proof language relies on the representation of the state of a proof after a logical rule has been applied. This information, which is usually meaningless from a logical point of view, is fundamental to describe the control mechanism of the proof search provided by the language. In this paper, we present a monadic datatype to represent the state information of a proof and we illustrate its use in the PVS theorem prover. We show how this representation can be used to design a new set of powerful tacticals for PVS, called PVS#, that have a simpler and clearer semantics compared to the semantics of standard PVS tacticals.     

ReSpecT Nets: Towards an Analysis Methodology for ReSpecT Specifications

A key feature for infrastructures providing coordination services is the ability to define the behaviour of coordination abstractions according to the requirements identified at design-time. We take as a representative for this scenario the logic-based language ReSpecT (Reaction Specification Tuples), used to program the reactive behaviour of tuple centres. ReSpecT specifications are at the core of the engineering methodology underlying the TuCSoN infrastructure, and are therefore the “conceptual place” where formal methods can be fruitfully applied to guarantee relevant system properties.In this paper we introduce ReSpecT nets, a formalism that can be used to describe reactive behaviours that can succeed and fail, and that allows for an encoding to Petri nets with inhibitor arcs. ReSpecT nets are introduced to give a core model to a fragment of the ReSpecT language, and to pave the way for devising an analysis methodology including formal verification of safety and liveness properties. In particular, we provide a semantics to ReSpecT specifications through a mapping to ReSpecT nets. The potential of this approach for the analysis of ReSpecT specifications is discussed, presenting initial results for the analysis of safety properties.     

OntoTrack: A semantic approach for ontology authoring

OntoTrackis an ontology authoring tool that combines a graph-based hierarchical layout and instant reasoning feedback within one single view. Currently OntoTrack can handle ontologies with an expressivity almost comparable to OWL Lite. The graphical representation provides an animated and zoomable subsumption graph with context sensitive features such as click-able miniature branches or selective detail views, together with drag-and-drop editing. Each editing step is instantly synchronised with an external reasoner in order to provide appropriate graphical feedback about relevant modeling consequences. A recent extention of OntoTrack provides an on-demand textual explanation for subsumption relationships between classes. This paper describes the key features of the current implementation and discusses future work, as well as some development issues. OntoTrack can be downloaded at http://www.informatik.uni-ulm.de/ki/ontotrack/.     

Synthesis of Optimal Strategies Using HyTech

Priced timed (game) automata extend timed (game) automata with costs on both locations and transitions. The problem of synthesizing an optimal winning strategy for a priced timed game under some hypotheses has been shown decidable in [P. Bouyer, F. Cassez, E. Fleury, and K.G. Larsen. Optimal strategies in priced timed game automata. Research Report BRICS RS-04-4, Denmark, Feb. 2004. Available at http://www.brics.dk/RS/04/4/]. In this paper, we present an algorithm for computing the optimal cost and for synthesizing an optimal strategy in case there exists one. We also describe the implementation of this algorithm with the tool HyTech and present an example.     

An integrated tool for loop calculations: aITALC

aITALC, a new tool for automating loop calculations in high energy physics, is described. The package creates Fortran code for two-fermion scattering processes automatically, starting from the generation and analysis of the Feynman graphs. We describe the modules of the tool, the intercommunication between them and illustrate its use with three examples.

Program summary

Title of the program:aITALC version 1.2.1 (9 August 2005)Catalogue identifier:ADWOProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWOProgram obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandComputer:PC i386Operating system:GNU/Linux, tested on different distributions SuSE 8.2 to 9.3, Red Hat 7.2, Debian 3.0, Ubuntu 5.04. Also on SolarisProgramming language used:GNU Make, Diana, Form, Fortran77Additional programs/libraries used:Diana 2.35 (Qgraf 2.0), Form 3.1, LoopTools 2.1 (FF)Memory required to execute with typical data:Up to about 10 MBNo. of processors used:1No. of lines in distributed program, including test data, etc.:40 926No. of bytes in distributed program, including test data, etc.:371 424Distribution format:tar gzip fileHigh-speed storage required:from 1.5 to 30 MB, depending on modules present and unfolding of examplesNature of the physical problem:Calculation of differential cross sections for e⁺e⁻ annihilation in one-loop approximation.Method of solution:Generation and perturbative analysis of Feynman diagrams with later evaluation of matrix elements and form factors.Restriction of the complexity of the problem:The limit of application is, for the moment, the 2→2 particle reactions in the electro-weak standard model.Typical running time:Few minutes, being highly depending on the complexity of the process and the Fortran compiler.     

An Isodata algorithm for straight line fitting

This note describes a method of fitting κ straight lines to a set of data points using an algorithm analogous to the Isodata, or κ-means, clustering technique for partitioning a set of data points into κ compact clusters.     

ASPIN: An all spin scattering code for atom-molecule rovibrationally inelastic cross sections

We present in this work a new computational code for the quantum calculation of integral cross sections for atom-molecule (linear) scattering processes. The atom is taken to be structureless while the molecule can be in its singlet, doublet, or triplet spin states and can be treated as either a rigid rotor or a rovibrational target. All the relevant state-to-state integral cross sections, and their sums over final states, can be calculated with the present code, for which we also describe in detail the various component routines.

Program summary

Program title: ASPINCatalogue identifier: AEBO_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEBO_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 99 596No. of bytes in distributed program, including test data, etc.: 1 267 615Distribution format: tar.gzProgramming language: Fortran/MPIComputer: AMD OPTERON COMPUTING SYSTEMS, model TYAN GX28 (B2882)Operating system: SuSE LINUX Professional 9RAM: 128 GBClassification: 2.6External routines: LAPACK/BLASNature of problem: Scattering of a diatomic molecule in its , , or spin states with an atom in its state. Partial and integral cross sections.Solution method: The coupled channel equations that describe the scattering process are solved through the propagation of the reactance K matrix employing a modification of the Variable Phase Method [1-3].Restrictions: Depending on the vib-rotational base used the problem may or may not fit into available RAM memory because all the runtime relevant quantities are stored on RAM memory instead of on disk.Additional comments: Both serial and parallel implementations of the program are provided. The CPC Librarian was not able to successfully run the parallel version.Running time: For simple and converged calculations a usual running time is in the order of a few minutes in the computer mentioned above, being shorter for the singlet and longer for the triplet.References:[1] F. Calogero, Variable Phase Approach to Potential Scattering, New York, 1967.[2] A. Degasperis, Il Nuovo Cimento 34 (1964) 1667.[3] C. Zemach, Il Nuovo Cimento 33 (1964) 939.     

A component- and push-based architectural style for ajax applications

A new breed of web application, dubbed ajax, is emerging in response to a limited degree of interactivity in large-grain stateless Web interactions. At the heart of this new approach lies a single page interaction model that facilitates rich interactivity. Also push-based solutions from the distributed systems are being adopted on the web for ajax applications. The field is, however, characterized by the lack of a coherent and precisely described set of architectural concepts. As a consequence, it is rather difficult to understand, assess, and compare the existing approaches. We have studied and experimented with several ajax frameworks trying to understand their architectural properties. In this paper, we summarize four of these frameworks and examine their properties and introduce the spiar architectural style which captures the essence of ajax applications. We describe the guiding software engineering principles and the constraints chosen to induce the desired properties. The style emphasizes user interface component development, intermediary delta-communication between client/server components, and push-based event notification of state changes through the components, to improve a number of properties such as user interactivity, user-perceived latency, data coherence, and ease of development. In addition, we use the concepts and principles to discuss various open issues in ajax frameworks and application development.     

Proofs of randomized algorithms in Coq

Randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distributions (Giry, Ramsey and Pfeffer). It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analyzing general recursive functions.We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the Coq proof assistant.     

Good programming in transactional memory : Game theory meets multicore architecture

In a multicore transactional memory (TM) system, concurrent execution threads interact and interfere with each other through shared memory. The less interference a thread provokes the better for the system. However, as a programmer is primarily interested in optimizing her individual code’s performance rather than the system’s overall performance, she does not have a natural incentive to provoke as little interference as possible. Hence, a TM system must be designed compatible with good programming incentives (GPI), i.e., writing efficient code for the overall system should coincide with writing code that optimizes an individual thread’s performance. We show that with most contention managers (CM) proposed in the literature so far, TM systems are not GPI compatible. We provide a generic framework for CMs that base their decisions on priorities and explain how to modify Timestamp-like CMs so as to feature GPI compatibility. In general, however, priority-based conflict resolution policies are prone to be exploited by selfish programmers. In contrast, a simple non-priority-based manager that resolves conflicts at random is GPI compatible.