Tool-supported invariant-based programming

The development of correct programs is a core problem in computer science. Although formal verification methods for establishing correctness with mathematical rigor are available, programmers often find these difficult to put into practice. One hurdle is deriving the loop invariants and proving that the code maintains them. So called correct-by-construction methods aim to alleviate this issue by integrating verification into the programming workflow. Invariant-based programming is a practical correct-by-construction method in which the programmer first establishes the invariant structure, and then incrementally extends the program in steps of adding code and proving after each addition that the code is consistent with the invariants. In this way, the program is kept internally consistent throughout its development, and the construction of the correctness arguments (proofs) becomes an integral part of the programming workflow. A characteristic of the approach is that programs are described as invariant diagrams, a graphical notation similar to the state charts familiar to programmers. Invariant-based programming is a new method that has not been evaluated in large scale studies yet. The most important prerequisite for feasibility on a larger scale is a high degree of automation. The goal of the Socos project has been to build tools to assist the construction and verification of programs using the method. This thesis describes the implementation and evaluation of a prototype tool in the context of the Socos project. The tool supports the drawing of the diagrams, automatic derivation and discharging of verification conditions, and interactive proofs. It is used to develop programs that are correct by construction. The tool consists of a diagrammatic environment connected to a verification condition generator and an existing state-of-the-art theorem prover. Its core is a semantics for translating diagrams into verification conditions, which are sent to the underlying theorem prover. We describe a concrete method for 1) deriving sufficient conditions for total correctness of an invariant diagram; 2) sending the conditions to the theorem prover for simplification; and 3) reporting the results of the simplification to the programmer in a way that is consistent with the invariantbased programming workflow and that allows errors in the program specification to be efficiently detected. The tool uses an efficient automatic proof strategy to prove as many conditions as possible automatically and lets the remaining conditions be proved interactively. The tool is based on the verification system PVS and i uses the SMT (Satisfiability Modulo Theories) solver Yices as a catch-all decision procedure. Conditions that were not discharged automatically may be proved interactively using the PVS proof assistant. The programming workflow is very similar to the process by which a mathematical theory is developed inside a computer supported theorem prover environment such as PVS. The programmer reduces a large verification problem with the aid of the tool into a set of smaller problems (lemmas), and he can substantially improve the degree of proof automation by developing specialized background theories and proof strategies to support the specification and verification of a specific class of programs. We demonstrate this workflow by describing in detail the construction of a verified sorting algorithm. Tool-supported verification often has little to no presence in computer science (CS) curricula. Furthermore, program verification is frequently introduced as an advanced and purely theoretical topic that is not connected to the workflow taught in the early and practically oriented programming courses. Our hypothesis is that verification could be introduced early in the CS education, and that verification tools could be used in the classroom to support the teaching of formal methods. A prototype of Socos has been used in a course at Åbo Akademi University targeted at first and second year undergraduate students. We evaluate the use of Socos in the course as part of a case study carried out in 2007.

Mechanical design and analysis of modular active magnetic bearing test rig

Tässä työssä on tutkittu modulaarisen aktiivimagneettilaakeroidun koelaitteen mekaanista suunnittelua ja analysointia. Suurnopeusroottorin suunnittelun teoria on esitelty. Lisäksi monia analyyttisiä mallinnusmenetelmiä mekaanisten kuormitusten mallintamiseksi on esitelty. Koska kyseessä on suurnopeussähkökone, roottoridynamiikka ja sen soveltuvuus suunnittelussa on esitelty. Magneettilaakerien rakenteeseen ja toimintaan on tutustuttu osana tätä työtä. Kirjallisuuskatsaus nykyisistä koelaitteista esimerkiksi komponenttien ominaisuuksien tunnistamiseen ja roottoridynamiikan tutkimuksiin on esitelty. Työn rajauksena on konseptisuunnittelu muunneltavalle magneettilaakeroidulle (AMB) koelaitteelle ja suunnitteluprosessin dokumentointi. Muunneltavuuteen päädyttiin, koska se mahdollistaa erilaisten komponenttiasetteluiden testaamisen erilaisille magneettilaakerikokoonpanoille ja roottoreille. Pääpaino tässä työssä on suurnopeus induktiokoneen roottorin suunnittelussa ja mallintamisessa. Modulaaristen toimilaitteiden kuten magneettilaakerien ja induktiosähkömoottorin rakenne on esitelty ja modulaarisen rakenteen käytettävyyden hyödyistä koelaitekäytössä on dokumentoitu. Analyyttisiä ja elementtimenetelmään perustuvia tutkimusmenetelmiä on käytetty tutkittaessa suunniteltua suurnopeusroottoria. Suunnittelun ja analysoinnin tulokset on esitelty ja verrattu keskenään eri mallinnusmenetelmien välillä. Lisäksi johtopäätökset sähkömagneettisten osien liittämisen monimutkaisuudesta ja vaatimuksista roottoriin ja toimilaitteisiin sekä mekaanisten että sähkömagneettisten ominaisuuksien optimoimiseksi on dokumentoitu.

Power properties if invariant tests for spatial autocorrelation in linear regression

This paper derives some exact power properties of tests for spatial autocorrelation in the context of a linear regression model. In particular, we characterize the circumstances in which the power vanishes as the autocorrelation increases, thus extending the work of Krämer (2005). More generally, the analysis in the paper sheds new light on how the power of tests for spatial autocorrelation is affected by the matrix of regressors and by the spatial structure. We mainly focus on the problem of residual spatial autocorrelation, in which case it is appropriate to restrict attention to the class of invariant tests, but we also consider the case when the autocorrelation is due to the presence of a spatially lagged dependent variable among the regressors. A numerical study aimed at assessing the practical relevance of the theoretical results is included

Stochastic perturbations to dynamical systems: a response theory approach

Using the formalism of the Ruelle response theory, we study how the invariant measure of an Axiom A dynamical system changes as a result of adding noise, and describe how the stochastic perturbation can be used to explore the properties of the underlying deterministic dynamics. We first find the expression for the change in the expectation value of a general observable when a white noise forcing is introduced in the system, both in the additive and in the multiplicative case. We also show that the difference between the expectation value of the power spectrum of an observable in the stochastically perturbed case and of the same observable in the unperturbed case is equal to the variance of the noise times the square of the modulus of the linear susceptibility describing the frequency-dependent response of the system to perturbations with the same spatial patterns as the considered stochastic forcing. This provides a conceptual bridge between the change in the fluctuation properties of the system due to the presence of noise and the response of the unperturbed system to deterministic forcings. Using Kramers-Kronig theory, it is then possible to derive the real and imaginary part of the susceptibility and thus deduce the Green function of the system for any desired observable. We then extend our results to rather general patterns of random forcing, from the case of several white noise forcings, to noise terms with memory, up to the case of a space-time random field. Explicit formulas are provided for each relevant case analysed. As a general result, we find, using an argument of positive-definiteness, that the power spectrum of the stochastically perturbed system is larger at all frequencies than the power spectrum of the unperturbed system. We provide an example of application of our results by considering the spatially extended chaotic Lorenz 96 model. These results clarify the property of stochastic stability of SRB measures in Axiom A flows, provide tools for analysing stochastic parameterisations and related closure ansatz to be implemented in modelling studies, and introduce new ways to study the response of a system to external perturbations. Taking into account the chaotic hypothesis, we expect that our results have practical relevance for a more general class of system than those belonging to Axiom A.

J-PMCRI: a methodology for inducing pre-pruned modular classification rules

Inducing rules from very large datasets is one of the most challenging areas in data mining. Several approaches exist to scaling up classification rule induction to large datasets, namely data reduction and the parallelisation of classification rule induction algorithms. In the area of parallelisation of classification rule induction algorithms most of the work has been concentrated on the Top Down Induction of Decision Trees (TDIDT), also known as the ‘divide and conquer’ approach. However powerful alternative algorithms exist that induce modular rules. Most of these alternative algorithms follow the ‘separate and conquer’ approach of inducing rules, but very little work has been done to make the ‘separate and conquer’ approach scale better on large training data. This paper examines the potential of the recently developed blackboard based J-PMCRI methodology for parallelising modular classification rule induction algorithms that follow the ‘separate and conquer’ approach. A concrete implementation of the methodology is evaluated empirically on very large datasets.

Wave-activity conservation laws and stability theorems for semi-geostrophic dynamics: part 2. pseudoenergy-based theory

This paper represents the second part of a study of semi-geostrophic (SG) geophysical fluid dynamics. SG dynamics shares certain attractive properties with the better known and more widely used quasi-geostrophic (QG) model, but is also a good prototype for balanced models that are more accurate than QG dynamics. The development of such balanced models is an area of great current interest. The goal of the present work is to extend a central body of QG theory, concerning the evolution of disturbances to prescribed basic states, to SG dynamics. Part 1 was based on the pseudomomentum; Part 2 is based on the pseudoenergy. A pseudoenergy invariant is a conserved quantity, of second order in disturbance amplitude relative to a prescribed steady basic state, which is related to the time symmetry of the system. We derive such an invariant for the semi-geostrophic equations, and use it to obtain: (i) a linear stability theorem analogous to Arnol'd's ‘first theorem’; and (ii) a small-amplitude local conservation law for the invariant, obeying the group-velocity property in the WKB limit. The results are analogous to their quasi-geostrophic forms, and reduce to those forms in the limit of small Rossby number. The results are derived for both the f-plane Boussinesq form of semi-geostrophic dynamics, and its extension to β-plane compressible flow by Magnusdottir & Schubert. Novel features particular to semi-geostrophic dynamics include apparently unnoticed lateral boundary stability criteria. Unlike the boundary stability criteria found in the first part of this study, however, these boundary criteria do not necessarily preclude the construction of provably stable basic states. The interior semi-geostrophic dynamics has an underlying Hamiltonian structure, which guarantees that symmetries in the system correspond naturally to the system's invariants. This is an important motivation for the theoretical approach used in this study. The connection between symmetries and conservation laws is made explicit using Noether's theorem applied to the Eulerian form of the Hamiltonian description of the interior dynamics.

Wave-activity conservation laws and stability theorems for semi-geostrophic dynamics: part 1. pseudomomentum-based theory

There exists a well-developed body of theory based on quasi-geostrophic (QG) dynamics that is central to our present understanding of large-scale atmospheric and oceanic dynamics. An important question is the extent to which this body of theory may generalize to more accurate dynamical models. As a first step in this process, we here generalize a set of theoretical results, concerning the evolution of disturbances to prescribed basic states, to semi-geostrophic (SG) dynamics. SG dynamics, like QG dynamics, is a Hamiltonian balanced model whose evolution is described by the material conservation of potential vorticity, together with an invertibility principle relating the potential vorticity to the advecting fields. SG dynamics has features that make it a good prototype for balanced models that are more accurate than QG dynamics. In the first part of this two-part study, we derive a pseudomomentum invariant for the SG equations, and use it to obtain: (i) linear and nonlinear generalized Charney–Stern theorems for disturbances to parallel flows; (ii) a finite-amplitude local conservation law for the invariant, obeying the group-velocity property in the WKB limit; and (iii) a wave-mean-flow interaction theorem consisting of generalized Eliassen–Palm flux diagnostics, an elliptic equation for the stream-function tendency, and a non-acceleration theorem. All these results are analogous to their QG forms. The pseudomomentum invariant – a conserved second-order disturbance quantity that is associated with zonal symmetry – is constructed using a variational principle in a similar manner to the QG calculations. Such an approach is possible when the equations of motion under the geostrophic momentum approximation are transformed to isentropic and geostrophic coordinates, in which the ageostrophic advection terms are no longer explicit. Symmetry-related wave-activity invariants such as the pseudomomentum then arise naturally from the Hamiltonian structure of the SG equations. We avoid use of the so-called ‘massless layer’ approach to the modelling of isentropic gradients at the lower boundary, preferring instead to incorporate explicitly those boundary contributions into the wave-activity and stability results. This makes the analogy with QG dynamics most transparent. This paper treats the f-plane Boussinesq form of SG dynamics, and its recent extension to β-plane, compressible flow by Magnusdottir & Schubert. In the limit of small Rossby number, the results reduce to their respective QG forms. Novel features particular to SG dynamics include apparently unnoticed lateral boundary stability criteria in (i), and the necessity of including additional zonal-mean eddy correlation terms besides the zonal-mean potential vorticity fluxes in the wave-mean-flow balance in (iii). In the companion paper, wave-activity conservation laws and stability theorems based on the SG form of the pseudoenergy are presented.

A unified theory of available potential energy

Traditional derivations of available potential energy, in a variety of contexts, involve combining some form of mass conservation together with energy conservation. This raises the questions of why such constructions are required in the first place, and whether there is some general method of deriving the available potential energy for an arbitrary fluid system. By appealing to the underlying Hamiltonian structure of geophysical fluid dynamics, it becomes clear why energy conservation is not enough, and why other conservation laws such as mass conservation need to be incorporated in order to construct an invariant, known as the pseudoenergy, that is a positive‐definite functional of disturbance quantities. The available potential energy is just the non‐kinetic part of the pseudoenergy, the construction of which follows a well defined algorithm. Two notable features of the available potential energy defined thereby are first, that it is a locally defined quantity, and second, that it is inherently definable at finite amplitude (though one may of course always take the small‐amplitude limit if this is appropriate). The general theory is made concrete by systematic derivations of available potential energy in a number of different contexts. All the well known expressions are recovered, and some new expressions are obtained. The possibility of generalizing the concept of available potential energy to dynamically stable basic flows (as opposed to statically stable basic states) is also discussed.

Towards a general theory of extremes for observables of chaotic dynamical systems

In this paper we provide a connection between the geometrical properties of the attractor of a chaotic dynamical system and the distribution of extreme values. We show that the extremes of so-called physical observables are distributed according to the classical generalised Pareto distribution and derive explicit expressions for the scaling and the shape parameter. In particular, we derive that the shape parameter does not depend on the cho- sen observables, but only on the partial dimensions of the invariant measure on the stable, unstable, and neutral manifolds. The shape parameter is negative and is close to zero when high-dimensional systems are considered. This result agrees with what was derived recently using the generalized extreme value approach. Combining the results obtained using such physical observables and the properties of the extremes of distance observables, it is possible to derive estimates of the partial dimensions of the attractor along the stable and the unstable directions of the flow. Moreover, by writing the shape parameter in terms of moments of the extremes of the considered observable and by using linear response theory, we relate the sensitivity to perturbations of the shape parameter to the sensitivity of the moments, of the partial dimensions, and of the Kaplan–Yorke dimension of the attractor. Preliminary numer- ical investigations provide encouraging results on the applicability of the theory presented here. The results presented here do not apply for all combinations of Axiom A systems and observables, but the breakdown seems to be related to very special geometrical configurations.

SINGULARITY THEORY AND FORCED SYMMETRY BREAKING IN EQUATIONS

A theory of bifurcation equivalence for forced symmetry breaking bifurcation problems is developed. We classify (O(2), 1) problems of corank 2 of low codimension and discuss examples of bifurcation problems leading to such symmetry breaking.

A new scale-invariant ratio and finite-size scaling for the stochastic susceptible-infected-recovered model

The critical behavior of the stochastic susceptible-infected-recovered model on a square lattice is obtained by numerical simulations and finite-size scaling. The order parameter as well as the distribution in the number of recovered individuals is determined as a function of the infection rate for several values of the system size. The analysis around criticality is obtained by exploring the close relationship between the present model and standard percolation theory. The quantity UP, equal to the ratio U between the second moment and the squared first moment of the size distribution multiplied by the order parameter P, is shown to have, for a square system, a universal value 1.0167(1) that is the same for site and bond percolation, confirming further that the SIR model is also in the percolation class.

A conformal invariant growth model

We present a one-parameter extension of the raise and peel one-dimensional growth model. The model is defined in the configuration space of Dyck (RSOS) paths. Tiles from a rarefied gas hit the interface and change its shape. The adsorption rates are local but the desorption rates are non-local; they depend not only on the cluster hit by the tile but also on the total number of peaks (local maxima) belonging to all the clusters of the configuration. The domain of the parameter is determined by the condition that the rates are non-negative. In the finite-size scaling limit, the model is conformal invariant in the whole open domain. The parameter appears in the sound velocity only. At the boundary of the domain, the stationary state is an adsorbing state and conformal invariance is lost. The model allows us to check the universality of non-local observables in the raise and peel model. An example is given.

The Hilbert space of the Chern-Simons theory on a cylinder: a loop quantum gravity approach

As a laboratory for loop quantum gravity, we consider the canonical quantization of the three-dimensional Chern-Simons theory on a noncompact space with the topology of a cylinder. Working within the loop quantization formalism, we define at the quantum level the constraints appearing in the canonical approach and completely solve them, thus constructing a gauge and diffeomorphism invariant physical Hilbert space for the theory. This space turns out to be infinite dimensional, but separable.

An Information Theory framework for two-stage binary image operator design

The design of translation invariant and locally defined binary image operators over large windows is made difficult by decreased statistical precision and increased training time. We present a complete framework for the application of stacked design, a recently proposed technique to create two-stage operators that circumvents that difficulty. We propose a novel algorithm, based on Information Theory, to find groups of pixels that should be used together to predict the Output Value. We employ this algorithm to automate the process of creating a set of first-level operators that are later combined in a global operator. We also propose a principled way to guide this combination, by using feature selection and model comparison. Experimental results Show that the proposed framework leads to better results than single stage design. (C) 2009 Elsevier B.V. All rights reserved.

NIELSEN COINCIDENCE THEORY OF FIBRE-PRESERVING MAPS AND DOLD`S FIXED POINT INDEX

Let M -> B, N -> B be fibrations and f(1), f(2): M -> N be a pair of fibre-preserving maps. Using normal bordism techniques we define an invariant which is an obstruction to deforming the pair f(1), f(2) over B to a coincidence free pair of maps. In the special case where the two fibrations axe the same and one of the maps is the identity, a weak version of our omega-invariant turns out to equal Dold`s fixed point index of fibre-preserving maps. The concepts of Reidemeister classes and Nielsen coincidence classes over B are developed. As an illustration we compute e.g. the minimal number of coincidence components for all homotopy classes of maps between S(1)-bundles over S(1) as well as their Nielsen and Reidemeister numbers.