Дисертації з теми "Higher-order theorie"

In this thesis I show is that it is possible to give modular correctness proofs of interesting higher-order imperative programs using higher-order separation logic. To do this, I develop a model higher-order imperative programming language, and develop a program logic for it. I demonstrate the power of my program logic by verifying a series of examples. This includes both realistic patterns of higher-order imperative programming such as the subject-observer pattern, as well as examples demonstrating the use of higher-order logic to reason modularly about highly aliased data structures such as the union-find disjoint set algorithm.

Thesis (MSc)--University of Stellenbosch, 2004.
ENGLISH ABSTRACT: Motivation for the study of protection strategies for graphs is rooted in antiquity and has evolved as a subdiscipline of graph theory since the early 1990s. Using, as a point of departure, the notions of weak Roman domination and secure domination (where protection of a graph is required against a single attack) an initial framework for higher order domination was introduced in 2002 (allowing for the protection of a graph against an arbitrary finite, or even infinite, number of attacks). In this thesis, the theory of higher order domination in graphs is broadened yet further to include the possibility of an arbitrary number of guards being stationed at a vertex. The thesis firstly provides a comprehensive survey of the combinatorial literature on Roman domination, weak Roman domination, secure domination and other higher order domination strategies, with a view to summarise the state of the art in the theory of higher order graph domination as at the start of 2004. Secondly, a generalised framework for higher order domination is introduced in two parts: the first catering for the protection of a graph against a finite number of consecutive attacks, and the second concerning the perpetual security of a graph (protection of the graph against an infinite number of consecutive attacks). Two types of higher order domination are distinguished: smart domination (requiring the existence of a protection strategy for any sequence of consecutive attacks of a pre–specified length, but leaving it up to a strategist to uncover such a guard movement strategy for a particular instance of the attack sequence), and foolproof domination (requiring that any possible guard movement strategy be a successful protection strategy for the graph in question). Properties of these higher order domination parameters are examined—first by investigating the application of known higher order domination results from the literature, and secondly by obtaining new results, thereby hopefully improving current understanding of these domination parameters. Thirdly, the thesis contributes by (i) establishing higher order domination parameter values for some special graph classes not previously considered (such as complete multipartite graphs, wheels, caterpillars and spiders), by (ii) summarising parameter values for special graph classes previously established (such as those for paths, cycles and selected cartesian products), and by (iii) improving higher order domination parameter bounds previously obtained (in the case of the cartesian product of two cycles). Finally, a clear indication of unresolved problems in higher order graph domination is provided in the conclusion to this thesis, together with some suggestions as to possibly desirable future generalisations of the theory.
AFRIKAANSE OPSOMMING: Die motivering vir die studie van verdedigingstrategie¨e vir grafieke het sy ontstaan in die antieke wˆereld en het sedert die vroe¨e 1990s as ’n subdissipline in grafiekteorie begin ontwikkel. Deur gebruik te maak van die idee van swak Romynse dominasie en versterkte dominasie (waar verdediging van ’n grafiek teen ’n enkele aanval vereis word) het ’n aanvangsraamwerk vir ho¨er– orde dominasie (wat ’n grafiek teen ’n veelvuldige, of selfs oneindige aantal, aanvalle verdedig) in 2002 die lig gesien. Die teorie van ho¨er–orde dominasie in grafieke word in hierdie tesis verbreed, deur toe te laat dat ’n arbitrˆere aantal wagte by elke punt van die grafiek gestasioneer mag word. Eerstens voorsien die tesis ’n omvangryke oorsig van die kombinatoriese literatuur oor Romynse dominasie, swak Romynse dominasie, versterkte dominasie en ander ho¨er–orde dominasie strategie ¨e, met die doel om die kundigheid betreffende die teorie van ho¨er–orde dominasie, soos aan die begin van 2004, op te som. Tweedens word ’n veralgemeende raamwerk vir ho¨er–orde dominasie bekendgestel, en wel in twee dele. Die eerste deel maak voorsiening vir die verdediging van ’n grafiek teen ’n eindige aantal opeenvolgende aanvalle, terwyl die tweede deel betrekking het op die oneindige sekuriteit van ’n grafiek (verdediging teen ’n oneindige aantal opeenvolgende aanvalle). Daar word tussen twee tipes h¨oer–orde dominasie onderskei: intelligente dominasie (wat slegs die bestaan van ’n verdedigingstrategie vir enige reeks opeenvolgende aanvalle vereis, maar dit aan ’n strateeg oorlaat om ’n suksesvolle bewegingstrategie vir die verdediging teen ’n spesifieke reeks aanvalle te vind), en onfeilbare dominasie (wat vereis dat enige moontlike bewegingstrategie resulteer in ’n suksesvolle verdedigingstrategie vir die betrokke grafiek). Eienskappe van hierdie ho¨er–orde dominasie parameters word ondersoek, deur eerstens die toepasbaarheid van bekende ho¨er–orde dominasie resultate vanuit die literatuur te assimileer, en tweedens nuwe resultate te bekom, in die hoop om die huidige kundigheid met betrekking tot hierdie dominasie parameters te verbreed. Derdens word ’n bydrae gelewer deur (i) ho¨er–orde dominasie parameterwaardes vas te stel vir sommige spesiale klasse grafieke wat nie voorheen ondersoek is nie (soos volledig veelledige grafieke, wiele, ruspers en spinnekoppe), deur (ii) parameterwaardes wat reeds bepaal is (soos byvoorbeeld di´e vir paaie, siklusse en sommige kartesiese produkte) op te som, en deur (iii) bekende ho¨er–orde dominasie parametergrense te verbeter (in die geval van die kartesiese produk van twee siklusse). Laastens word ’n aanduiding van oop probleme in die teorie van ho¨er–orde dominasie in die slothoofstuk van die tesis voorsien, tesame met voorstelle ten opsigte van moontlik sinvolle veralgemenings van die teorie.

Thesis (M.S. in Applied Mathematics)--Naval Postgraduate School, June 2002.
Thesis advisor(s): Harold Fredricksen, Craig W. Rasmussen. Includes bibliographical references (p. 45-46). Also available online.

Things could have been different, but could it also have been different what things there are? It is natural to think so, since I could have failed to be born, and it is natural to think that I would then not have been anything. But what about entities like propositions, properties and relations? Had I not been anything, would there have been the property of being me? In this thesis, I formally develop and assess views according to which it is both contingent what individuals there are and contingent what propositions, properties and relations there are. I end up rejecting these views, and conclude that even if it is contingent what individuals there are, it is necessary what propositions, properties and relations there are. Call the view that it is contingent what individuals there are first-order contingentism, and the view that it is contingent what propositions, properties and relations there are higher-order contingentism. I bring together the three major contributions to the literature on higher-order contingentism, which have been developed largely independently of each other, by Kit Fine, Robert Stalnaker, and Timothy Williamson. I show that a version of Stalnaker's approach to higher-order contingentism was already explored in much more technical detail by Fine, and that it stands up well to the major challenges against higher-order contingentism posed by Williamson. I further show that once a mistake in Stalnaker's development is corrected, each of his models of contingently existing propositions corresponds to the propositional fragment of one of Fine's more general models of contingently existing propositions, properties and relations, and vice versa. I also show that Stalnaker's theory of contingently existing propositions is in tension with his own theory of counterfactuals, but not with one of the main competing theories, proposed by David Lewis. Finally, I connect higher-order contingentism to expressive power arguments against first-order contingentism. I argue that there are intelligible distinctions we draw with talk about "possible things", such as the claim that there are uncountably many possible stars. Since first-order contingentists hold that there are no possible stars apart from the actual stars, they face the challenge of paraphrasing such talk. I show that even in an infinitary higher-order modal logic, the claim that there are uncountably many possible stars can only be paraphrased if higher-order contingentism is false. I therefore conclude that even if first-order contingentism is true, higher-order contingentism is false.

We undertake an asymptotic study of a second Painlevé hierarchy based on the Jimbo-Miwa Lax pair in the limit as the independent variable approaches infinity. The hierarchy is defined by an infinite sequence of non-linear ordinary differential equations, indexed by order, with the classical second Painlevé equation as the first member. We investigate general and special asymptotic behaviours admitted by each equation in the hierarchy. We show that the general asymptotic behaviour is described by two related hyperelliptic functions, where the genus of the functions increases with each member of the hierarchy, and we prove that there exist special families of solutions which are represented by algebraic formal power series. For specific values of the constants which appear in the higher-order second Painlevé equations, exact solutions are also constructed. Particular attention is given to the fourth-order analogue of the classical second Painlevé equation. In this case, the general asymptotic behaviour is given to leading-order by two related genus-2 hyperelliptic functions. These functions are characterised by four complex parameters which depend on the independent variable through the perturbation terms of the leading-order equations, and we investigate how these parameters change with respect to this variable. We also show that the fourth-order equation admits two classes of algebraic formal power series and that there exist families of true solutions with these behaviours in specified sectors of the complex plane, as well as unique solutions in extended sectors. To complement our asymptotic study of higher-order Painlevé equations, we consider a new setting in which classical Painlevé equations arise. We study reaction-diffusion equations with quadratic and cubic source terms, with a spatio-temporal dependence included in those terms, and show that solutions of these equations are given by first and second Painlevé transcendents.

Doctor of Philosophy (PhD)
We undertake an asymptotic study of a second Painlevé hierarchy based on the Jimbo-Miwa Lax pair in the limit as the independent variable approaches infinity. The hierarchy is defined by an infinite sequence of non-linear ordinary differential equations, indexed by order, with the classical second Painlevé equation as the first member. We investigate general and special asymptotic behaviours admitted by each equation in the hierarchy. We show that the general asymptotic behaviour is described by two related hyperelliptic functions, where the genus of the functions increases with each member of the hierarchy, and we prove that there exist special families of solutions which are represented by algebraic formal power series. For specific values of the constants which appear in the higher-order second Painlevé equations, exact solutions are also constructed. Particular attention is given to the fourth-order analogue of the classical second Painlevé equation. In this case, the general asymptotic behaviour is given to leading-order by two related genus-2 hyperelliptic functions. These functions are characterised by four complex parameters which depend on the independent variable through the perturbation terms of the leading-order equations, and we investigate how these parameters change with respect to this variable. We also show that the fourth-order equation admits two classes of algebraic formal power series and that there exist families of true solutions with these behaviours in specified sectors of the complex plane, as well as unique solutions in extended sectors. To complement our asymptotic study of higher-order Painlevé equations, we consider a new setting in which classical Painlevé equations arise. We study reaction-diffusion equations with quadratic and cubic source terms, with a spatio-temporal dependence included in those terms, and show that solutions of these equations are given by first and second Painlevé transcendents.

This thesis investigates higher order asymptotic properties of a semiparametric averaged derivative estimator. Classical parametric models assume that we know the distribution function of random variables of interest up to finite dimensional parameters, while nonparametric models do not assume this knowledge. Parametric estimators typically enjoy - consistency and asymptotic normality under certain conditions, while nonparametric estimators converge to the true functionals of interest slower than parametric ones. Semiparametric estimators, a compromise between the two, have been intensively studied since the 1970s. Some of them have been shown to have the same convergence rate as parametric estimators despite involving nonparametric functional estimates. Semiparametric methods often suit econometrics because economic theory typically does not provide the whole information on economic variables which parametric methods require, and a sample of very large size is rarely available in econometrics. This thesis treats a semiparametric averaged derivative estimator of single index models. Its first order asymptotic theory has been studied since late 1980s. It has been shown to be n-consistent and asymptotically normally distributed under certain regularity conditions despite involving a nonparametric density estimate. However its higher order properties could be affected by the property of nonparametric estimates. We obtain valid Edgeworth expansions for both normalized and studentized estimators, and moreover show the bootstrap distribution approximates the exact distribution of the estimator asymptotically as well as the Edgeworth expansion for the normalized statistics. We propose optimal bandwidth choices which minimize the normal approximation error using the expansion. We also examine the finite sample performance of the Edgeworth expansions by a Monte Carlo study.

Geometrical physics is a relatively young branch of applied mathematics that was initiated by the 60's and the 70's when A. Lichnerowicz, W.M. Tulczyjew and J.M. Souriau, among many others, began to study various topics in physics using methods of differential geometry. This "geometrization" provides a way to analyze the features of the physical systems from a global viewpoint, thus obtaining qualitative properties that help us in the integration of the equations that describe them. Since then, there has been a strong development in the intrinsic treatment of a variety of topics in theoretical physics, applied mathematics and control theory using methods of differential geometry. Most of the work done in geometrical physics since its first days has been devoted to study first-order theories, that is, those theories whose physical information depends on (at most) first-order derivatives of the generalized coordinates of position (velocities). However, there are theories in physics in which the physical information depends explicitly on accelerations or higher-order derivatives of the generalized coordinates of position, and thus more sophisticated geometrical tools are needed to model them acurately. In this Ph.D. Thesis we pretend to give a geometrical description of some of these higher-order theories. In particular, we focus on dynamical systems and field theories whose dynamical information can be given in terms of a Lagrangian function, or a Hamiltonian that admits Lagrangian counterpart. More precisely, we will use the Lagrangian-Hamiltonian unified approach in order to develop a geometric framework for autonomous and non-autonomous higher-order dynamical system, and for second-order field theories. This geometric framework will be used to study several relevant physical examples and applications, such as the Hamilton-Jacobi theory for higher-order mechanical systems, relativistic spin particles and deformation problems in mechanics, and the Korteweg-de Vries equation and other systems in field theory.
La física geomètrica és una branca relativament jove de la matemàtica aplicada que es va iniciar als anys 60 i 70 qua A. Lichnerowicz, W.M. Tulczyjew and J.M. Souriau, entre molts altres, van començar a estudiar diversos problemes en física usant mètodes de geometria diferencial. Aquesta "geometrització" proporciona una manera d'analitzar les característiques dels sistemes físics des d'una perspectiva global, obtenint així propietats qualitatives que faciliten la integració de les equacions que els descriuen. D'ençà s'ha produït un fort desenvolupamewnt en el tractament intrínsic d'una gran varietat de problemes en física teòrica, matemàtica aplicada i teoria de control usant mètodes de geometria diferencial. Gran part del treball realitzat en la física geomètrica des dels seus primers dies s'ha dedicat a l'estudi de teories de primer ordre, és a dir, teories tals que la informació física depèn en, com a molt, derivades de primer ordre de les coordenades de posició generalitzades (velocitats). Tanmateix, hi ha teories en física en les que la informació física depèn de manera explícita en acceleracions o derivades d'ordre superior de les coordenades de posició generalitzades, requerint, per tant, d'eines geomètriques més sofisticades per a modelar-les de manera acurada. En aquesta Tesi Doctoral ens proposem donar una descripció geomètrica d'algunes d'aquestes teories. En particular, estudiarem sistemes dinàmics i teories de camps tals que la seva informació dinàmica ve donada en termes d'una funció lagrangiana, o d'un hamiltonià que prové d'un sitema lagrangià. Per a ser més precisos emprarem la formulació unificada Lagrangiana-Hamiltoniana per tal de desenvolupar marcs geomètrics per a sistemes dinàmics d'ordre superior autònoms i no autònoms, i per a teories de camps de segon ordre. Amb aquest marc geomètric estudiarem alguns exemples físics rellevants i algunes aplicacions, com la teoria de Hamilton-Jacobi per a sistemes mecànics d'ordre superior, partícules relativístiques amb spin i problemes de deformació en mecànica, i l'equació de Korteweg-de Vries i altres sistemes en teories de camps.

The Post-Newtonian limit of a fourth-order metric theory of gravity is discussed, based on the most general quadratic Lagrangian. This approach involves the use of the perturbation expansion of the metric tensor, extended up to the fourth-order and expressed in terms of three gravitational potentials. The analysis concerns the search and the resolution, where possible, of systems of coupled fourth-order differential equations, obtained by varying the conditions placed on the coupling constants appearing in the Lagrangian. The solutions are computed using the Green’s function method. Finally, the gravitational potentials thus obtained are compared with the Newtonian one derived in General Relativity in the weak-field and low-veocity limit.

Higher-order recursion schemes are a powerful model of functional computation that grew out of traditional recursive program schemes and generalisations of grammars. It is common to view recursion schemes as generators of possibly-infinite trees, which Ong showed to have a decidable monadic second order theory and opened the door to applications in verification. Kobayashi later presented an intersection type characterisation of the model checking problem, on which most subsequent applied work is based. In recent work, recursion schemes have been considered to play a role similar to Boolean programs in verification of first-order imperative programs: a natural target for abstraction of programs with very large or infinite data domains. In this thesis we focus on the development of model checking algorithms for variants of recursion schemes. We start our contributions with a model checking algorithm inspired by the fully abstract game semantics of recursion schemes, but specified as a goal-directed approach to intersection type inference, that offers a unification of the views of Ong and Kobayashi. We build on this largely theoretical contribution with two orthogonal extensions and practical implementations. First, we develop a new extension of recursion schemes: higher-order recursion schemes with cases, which add non-determinism and a case construct operating over a finite data domain. These additions provide us with a more natural and succinct target for abstraction from functional programs: encoding data using functions inevitably results in an increase in the order and arity of the scheme, which have a direct impact on the worst-case complexity of the problem. We characterise the model checking problem using a novel intersection and union type system and give a practical algorithm for type inference in this system. We have carried out an empirical evaluation of the implementation --- the tool T_RAVMC --- using a variety of problem instances from the literature and a new suite of problem instances derived via an abstraction-refinement procedure from functional programs. Second, we extend our approach from safety properties to all properties expressible in monadic second order logic using alternating parity tree automata as our specification language. We again provide an implementation and an empirical evaluation, which shows that despite the challenges accompanying liveness properties our tool scales beyond the current state of the art.

In this thesis we take as our starting point the existing theory of higher-order algebra developed by K. Meinke and B. Möller. We will both apply and extend this theory. To illustrate the use of higher-order algebra as a formalism for formal specification and verification we present two case studies. In the first case study we consider the formal specification of two systolic algorithms for convolution. We formally verify the correctness of these two algorithms using higher-order equational logic and investigate the metamathematics of our verification proofs. The second case study considers the correctness of a dataflow algorithm for computing the Hamming stream. We present a non-constructive higher-order Horn specification of the Hamming stream and develop a semantic proof to verify the correctness of the dataflow algorithm. This second case study illustrates the power of higher-order algebraic methods using non-constructive techniques to capture abstract properties of the Hamming stream. For specification in the large we need to be able to structure specifications in a modular fashion and allow for the reuse of specifications. To this end we present a theory of parameterised higher-order specifications. We take a standard theory of parameterised first-order specifications and extend it to the higher-order case. We demonstrate our theory by presenting a parameterised specification of convolution in which the stream space is a parameter. One of the limitations of higher-order algebra using only ? and → types is the difficulty in modelling objects which are parametric in type, such as polymorphic functions, generic data structures and infinite families of algorithms and architectures. We propose to overcome this limitation by extending the type system of higher-order algebra with limit types. We refer to the resulting theory as higher-order algebra with transfinite types. The idea is that a limit type contains all the types below it in a natural transfinite type hierarchy and thus provides a "universal" type in which all the lower types can be embedded.

Density functional theory (DFT) is not only an accurate but also a widely used theory for describing the quantum-mechanical electronic structure of matter. In this approach, the intractable problem of interacting electrons is simplified to a tractable problem of non-interacting electrons moving in an effective potential. Even with this simplification, DFT remains extremely computationally expensive. In particular, DFT scales cubically with respect to the number of atoms, which restricts the size of systems that can be studied. Orbital free density functional theory (OF-DFT) represents a simplification of DFT applicable to metallic systems that behave like a free-electron gas. Current implementations of OF-DFT employ the plane-wave basis, the global nature of the basis prevents the efficient use of modern high-performance computer archi- tectures. We present a real-space formulation and higher-order finite-difference implementation of periodic Orbital-free Density Functional Theory (OF-DFT). Specifically, utilizing a local reformulation of the electrostatic and kernel terms, we develop a gener- alized framework suitable for performing OF-DFT simulations with different variants of the electronic kinetic energy. In particular, we develop a self-consistent field (SCF) type fixed-point method for calculations involving linear-response kinetic energy functionals. In doing so, we make the calculation of the electronic ground-state and forces on the nuclei amenable to computations that altogether scale linearly with the number of atoms. We develop a parallel implementation of our method using Portable, Extensible Toolkit for scientific computations (PETSc) suite of data structures and routines. The communication between processors is handled via the Message Passing Interface(MPI). We implement this formulation using the finite-difference discretization, us- ing which we demonstrate that higher-order finite-differences can achieve relatively large convergence rates with respect to mesh-size in both the energies and forces. Additionally, we establish that the fixed-point iteration converges rapidly, and that it can be further accelerated using extrapolation techniques like Anderson mixing. We verify the accuracy of our results by comparing the energies and forces with plane-wave methods for selected examples, one of which is the vacancy formation energy in Aluminum. Overall, we demonstrate that the proposed formulation and implementation is an attractive choice for performing OF-DFT calculations.

Les comportements des processus concurrents peuvent être exprimés en utilisant des calculs de processus, des langages formels simples qui permettent de démontrer des résultats mathématiques précis sur les interactions entre processus. Un exemple très simple est CCS, un autre exemple est le pi-calcul, plus expressif grâce à un mécanisme de communication de canaux. Dans ce dernier, on peut instaurer un système de types (pour raffiner l'analyse aux environnements plus contraints) et encoder le lambda-calcul (qui représente les calculs séquentiels).Certains de ces calculs, comme CCS ou des variantes du pi-calcul comme les calculs de fusions, ont une certaine propriété de symétrie. On utilise dans un premier temps cette symétrie comme un outil, pour prouver que deux encodages du lambda-calcul dans le pi-calcul sont en fait équivalents.Cette preuve nécessitant un système de types et une forme de symétrie, on se pose la question de l'existence d'un système de types pour les autres calculs symétriques, notamment les calculs de fusion, à laquelle on répond par la négative avec un théorème d'impossibilité.En analysant ce théorème, on découvre un contrainte fondamentale de ces calculs qui empêche l'utilisation des types, à savoir la présence d'une notion de relation d'équivalence entre les canaux de communication. Le relâchement de cette contrainte pour obtenir une relation de pré-ordre engendre un calcul intéressant qui recouvre des notions importantes du pi-calcul, absentes dans les calculs de fusion : les types et les noms privés. La première partie de la thèse se concentre sur l'étude de ce calcul.La deuxième partie de la thèse se concentre sur la bisimulation, une méthode pour établir l'équivalence de deux agents dans des langages d'ordre supérieur, par exemple le pi-calcul ou le lambda-calcul. Une amélioration de cette méthode est la théorie des techniques modulo, très puissante, mais qui malheureusement s'applique uniquement aux systèmes de premier ordre, comme les automates ou CCS.Cette thèse s'applique alors à décrire les langages d'ordre supérieur en tant que systèmes du premier ordre. On récupère ainsi la théorie générale des techniques modulo pour ces langages, en prouvant correctes la correspondance induite et les techniques spécifiques à chaque langage. On détaille les tenants et aboutissants de cette approche, pour fournir les outils nécessaires à son utilisation pour d'autres langages d'ordre supérieur
The behaviours of concurrent processes can be expressed using process calculi, which are simple formal languages that let us establish precise mathematical results on the behaviours and interactions between processes. A very simple example is CCS, another one is the pi-calculus, which is more expressive thanks to a name-passing mechanism. The pi-calculus supports the addition of type systems (to refine the analysis to more subtle environments) and the encoding of the lambda-calculus (which represents sequential computations).Some of these calculi, like CCS or variants of the pi-calculus such as fusion calculi, enjoy a property of symmetry. First, we use this symmetry as a tool to prove that two encodings of the lambda-calculus in the pi-calculus are in fact equivalent.This proof using a type system and a form of symmetry, we wonder if other existing symmetric calculi can support the addition of type systems. We answer negatively to this question with an impossibility theorem.Investigating this theorem leads us to a fundamental constraint of these calculi that forbids types: they induce an equivalence relation on names. Relaxing this constraint to make it a preorder relation yields another calculus that recovers important notions of the pi-calculus, that fusion calculi do not satisfy: the notions of types and of privacy of names. The first part of this thesis focuses on the study of this calculus, a pi-calculus with preorders on names.The second part of this thesis focuses on bisimulation, a proof method for equivalence of agents in higher-order languages, like the pi- or the lambda-calculi. An enhancement of this method is the powerful theory of bisimulations up to, which unfortunately only applies for first-order systems, like automata or CCS.We then proceed to describe higher-order languages as first-order systems. This way, we inherit the general theory of up-to techniques for these languages, by proving correct the translations and up-to techniques that are specific to each language. We give details on the approach, to provide the necessary tools for future applications of this method to other higher-order languages

The calculation of higher order corrections in perturbative quantum field theories is a particularly important subject. Our current model for particle physics is the stan- dard model; a quantum field theory which has served to describe a huge amount of observed data very well. As the Large Hadron Collider is collecting more and more high energy data with smaller and smaller experimental errors, the accuracy of theoretical calculations must keep up with experiment in order to discriminate be- tween physics arising from our current standard model, and beyond standard model physics. In chapter 2 we give a brief introduction to the fundamentals of perturbative quan- tum field theories, with particular emphasis on Quantum ChromoDynamics, where higher order calculations are particularly important due to the fact that αs (M_Z) >> α. In chapter 3 we present a review of methods for calculations within perturbative quantum field theories, both for real and virtual corrections. In chap- ter 4 we give a detailed explanation of the method of sector decomposition, and highlight how it can be applied to the calculation of multi-parameter polynomial integrals, which appear widely in high energy physics, and in particular within the higher order calculations of perturbative quantum field theories. In chapter 5 we present SecDec - a publicly available computer code which implements sector de- composition. We give a range of examples to demonstrate its power in calculating various integrals appearing in higher order calculations in perturbative quantum field theories.

In recent years advances in technology have allowed the transition of composite structures from secondary to primary structural components. Consequently, a lot of applications demand development of thicker composite structures to sustain heavier loads. Typical sandwich panels consist of two thin metallic or composite face sheets separated by a honeycomb or foam core. This configuration gives the sandwich panel high stiffness and strength and enables excellent energy absorption capabilities with little resultant weight penalty. This makes sandwich structures a preferred design for a lot of applications including aerospace, naval, wind turbines and civil industries. Most aerospace structures can be analyzed using shell and plate models and many such structures are modeled as composite sandwich plates and shells. Accurate theoretical formulations that minimize the CPU time without penalties on the quality of the results are thus of fundamental importance. The classical plate theory (CPT) and the first order shear deformation theory (FSDT) are the simplest equivalent single-layer models, and they adequately describe the kinematic behavior of most laminates where the difference between the stiffnesses of the respective phases is not huge. However, in the case of sandwich structures where the core is a much more compliant and softer material as compared to the face sheets the results from CPT and FSDT becomes highly inaccurate. Higher order theories in such cases can represent the kinematics better, may not require shear correction factors, and can yield much more accurate results. An advanced Extended Higher-order Sandwich Panel Theory (EHSAPT) which is a two-dimensional extension of the EHSAPT beam model that Phan presented is developed. Phan had extended the HSAPT theory for beams that allows for the transverse shear distribution in the core to acquire the proper distribution as the core stiffness increases as a result of non-negligible in-plane stresses. The HSAPT model is incapable of capturing the in-plane stresses and assumes negligible in-plane rigidity. The current research extends that concept and applies it to two-dimensional plate structures with variable aspect ratios. The theory assumes a transverse displacement in the core that varies as a second order equation in z and the in-plane displacements that are of third order in z, the transverse coordinate. This approach allows for five generalized coordinates in the core (the in-plane and transverse displacements and two rotations about the x and y-axes respectively). The major assumptions of the theory are as follows: 1) The face sheets satisfy the Euler-Bernoulli assumptions, and their thicknesses are small compared to the overall thickness of the sandwich section; they undergo small strains with moderate rotations. 2) The core is compressible in the transverse and axial directions; it has in-plane, transverse and shear rigidities. 3) The bonding between the face sheets and the core is assumed to be perfect. The kinematic model is developed by assuming a displacement field for the soft core and then enforcing continuity of the displacement field across the interface between the core and facesheets. The constitutive relations are then defined, and variational and energy techniques are employed to develop the governing equations and associated boundary conditions. A static loading case for a simply supported sandwich plate is first considered, and the results are compared to existing solutions from Elasticity theory, Classical Plate Theory (CPT) and First-Order Shear Deformation Plate Theory (FSDT). Subsequently, the governing equations for a dynamic analysis are developed for a laminated sandwich plate. A free vibration problem is analyzed for a simply supported laminated sandwich plate, and the results for the fundamental natural frequency are compared to benchmark elasticity solutions provided by Noor. After validation of the new Extended Higher Order Sandwich Panel Theory (EHSAPT), a parametric study is carried out to analyze the effect of variation of various geometric and material properties on the fundamental natural frequency of the structure. After the necessary verification and validation of the theory by comparing static and free vibration results to elasticity solutions, a nonlinear static analysis for square and rectangular plates is carried out under various sets of boundary conditions. The analysis was carried out using variational techniques, and the Ritz method was used to find an approximate solution. The kinematics were developed for a sandwich plate undergoing small strain and moderate rotations and nonlinear strain displacement relations were evaluated. Approximate and assumed solutions satisfying the geometric boundary conditions were developed and substituted in the total potential energy relations. After carrying out the spatial integrations, the total potential energy was then minimized with respect to the unknown coefficients in the assumed solution resulting in nonlinear simultaneous algebraic equations for the unknown coefficients. The simultaneous nonlinear equations were then solved using the Newton-Raphson method. A convergence study was carried out to study the effect of varying the number of terms in the approximate solution on the overall result and rapid convergence was observed. The rapid convergence can be attributed to the fact that the assumed approximate solution not only satisfies the geometric boundary conditions of the problem but also the natural boundary conditions. During calculations four cases of boundary conditions were considered 1) Simply Supported with moveable edges. 2) Simply Supported with fixed edges. 3) Clamped with moveable edges. 4) Clamped with fixed edges. For movable boundary conditions, in-plane displacements along the normal direction to the supported edges are allowed whereas the out-of-plane displacement is fixed. For the immovable boundary condition cases, the plate is prevented from both in-plane and out-of-plane displacements along the edges. For the simply supported cases rotations about the tangential direction are allowed, and for the clamped cases no rotations are allowed.In recent years advances in technology have allowed the transition of composite structures from secondary to primary structural components. Consequently, a lot of applications demand development of thicker composite structures to sustain heavier loads. Typical sandwich panels consist of two thin metallic or composite face sheets separated by a honeycomb or foam core. This configuration gives the sandwich panel high stiffness and strength and enables excellent energy absorption capabilities with little resultant weight penalty. This makes sandwich structures a preferred design for a lot of applications including aerospace, naval, wind turbines and civil industries. Most aerospace structures can be analyzed using shell and plate models and many such structures are modeled as composite sandwich plates and shells. Accurate theoretical formulations that minimize the CPU time without penalties on the quality of the results are thus of fundamental importance. The classical plate theory (CPT) and the first order shear deformation theory (FSDT) are the simplest equivalent single-layer models, and they adequately describe the kinematic behavior of most laminates where the difference between the stiffnesses of the respective phases is not huge. However, in the case of sandwich structures where the core is a much more compliant and softer material as compared to the face sheets the results from CPT and FSDT becomes highly inaccurate. Higher order theories in such cases can represent the kinematics better, may not require shear correction factors, and can yield much more accurate results. An advanced Extended Higher-order Sandwich Panel Theory (EHSAPT) which is a two-dimensional extension of the EHSAPT beam model that Phan presented is developed. Phan had extended the HSAPT theory for beams that allows for the transverse shear distribution in the core to acquire the proper distribution as the core stiffness increases as a result of non-negligible in-plane stresses. The HSAPT model is incapable of capturing the in-plane stresses and assumes negligible in-plane rigidity. The current research extends that concept and applies it to two-dimensional plate structures with variable aspect ratios. The theory assumes a transverse displacement in the core that varies as a second order equation in z and the in-plane displacements that are of third order in z, the transverse coordinate. This approach allows for five generalized coordinates in the core (the in-plane and transverse displacements and two rotations about the x and y-axes respectively). The major assumptions of the theory are as follows: 1) The face sheets satisfy the Euler-Bernoulli assumptions, and their thicknesses are small compared to the overall thickness of the sandwich section; they undergo small strains with moderate rotations. 2) The core is compressible in the transverse and axial directions; it has in-plane, transverse and shear rigidities. 3) The bonding between the face sheets and the core is assumed to be perfect. The kinematic model is developed by assuming a displacement field for the soft core and then enforcing continuity of the displacement field across the interface between the core and facesheets. The constitutive relations are then defined, and variational and energy techniques are employed to develop the governing equations and associated boundary conditions. A static loading case for a simply supported sandwich plate is first considered, and the results are compared to existing solutions from Elasticity theory, Classical Plate Theory (CPT) and First-Order Shear Deformation Plate Theory (FSDT). Subsequently, the governing equations for a dynamic analysis are developed for a laminated sandwich plate. A free vibration problem is analyzed for a simply supported laminated sandwich plate, and the results for the fundamental natural frequency are compared to benchmark elasticity solutions provided by Noor. After validation of the new Extended Higher Order Sandwich Panel Theory (EHSAPT), a parametric study is carried out to analyze the effect of variation of various geometric and material properties on the fundamental natural frequency of the structure. After the necessary verification and validation of the theory by comparing static and free vibration results to elasticity solutions, a nonlinear static analysis for square and rectangular plates is carried out under various sets of boundary conditions. The analysis was carried out using variational techniques, and the Ritz method was used to find an approximate solution. The kinematics were developed for a sandwich plate undergoing small strain and moderate rotations and nonlinear strain displacement relations were evaluated. Approximate and assumed solutions satisfying the geometric boundary conditions were developed and substituted in the total potential energy relations. After carrying out the spatial integrations, the total potential energy was then minimized with respect to the unknown coefficients in the assumed solution resulting in nonlinear simultaneous algebraic equations for the unknown coefficients. The simultaneous nonlinear equations were then solved using the Newton-Raphson method. A convergence study was carried out to study the effect of varying the number of terms in the approximate solution on the overall result and rapid convergence was observed. The rapid convergence can be attributed to the fact that the assumed approximate solution not only satisfies the geometric boundary conditions of the problem but also the natural boundary conditions. During calculations four cases of boundary conditions were considered 1) Simply Supported with moveable edges. 2) Simply Supported with fixed edges. 3) Clamped with moveable edges. 4) Clamped with fixed edges. For movable boundary conditions, in-plane displacements along the normal direction to the supported edges are allowed whereas the out-of-plane displacement is fixed. For the immovable boundary condition cases, the plate is prevented from both in-plane and out-of-plane displacements along the edges. For the simply supported cases rotations about the tangential direction are allowed, and for the clamped cases no rotations are allowed.

Thesis (M.S.)--West Virginia University, 2004.
Title from document title page. Document formatted into pages; contains xi, 126 p. : ill. Includes abstract. Includes bibliographical references (p. 123-126).

We present a series of improvements to the Hybrid system, a formal theory implemented in Isabelle/HOL to support specifying and reasoning about formal systems using higher-order abstract syntax (HOAS). We modify Hybrid's type of terms, which is built definitionally in terms of de Bruijn indices, to exclude at the type level terms with `dangling' indices. We strengthen the injectivity property for Hybrid's variable-binding operator, and develop rules for compositional proof of its side condition, avoiding conversion from HOAS to de Bruijn indices. We prove representational adequacy of Hybrid (with these improvements) for a lambda-calculus-like subset of Isabelle/HOL syntax, at the level of set-theoretic semantics and without unfolding Hybrid's definition in terms of de Bruijn indices. In further work, we prove an induction principle that maintains some of the benefits of HOAS even for open terms. We also present a case study of the formalization in Hybrid of a small programming language, Mini-ML with mutable references, including its operational semantics and a type-safety property. This is the largest case study in Hybrid to date, and the first to formalize a language with mutable references. We compare four variants of this formalization based on the two-level approach adopted by Felty and Momigliano in other recent work on Hybrid, with various specification logics (SLs), including substructural logics, formalized in Isabelle/HOL and used in turn to encode judgments of the object language. We also compare these with a variant that does not use an intermediate SL layer. In the course of the case study, we explore and develop new proof techniques, particularly in connection with context invariants and induction on SL statements.

This thesis studies the categorical formalisation of quantum computing, through the prism of type theory, in a three-tier process. The first stage of our investigation involves the creation of the dagger lambda calculus, a lambda calculus for dagger compact categories. Our second contribution lifts the expressive power of the dagger lambda calculus, to that of a quantum programming language, by adding classical control in the form of complementary classical structures and dualisers. Finally, our third contribution demonstrates how our lambda calculus can be applied to various well known problems in quantum computation: Quantum Key Distribution, the quantum Fourier transform, and the teleportation protocol.

This thesis examines the use of game semantics for the automatic equivalence checking of higher-order programs. Game semantics has proved to be a powerful method for constructing fully abstract models of logics and programming languages. Furthermore, the concrete nature of the semantics lends itself to algorithmic analysis. The game-semantic model can be used to identify fragments of languages which have a decidable observational equivalence problem. We investigate decidability results for different languages as well as the efficiency of these algorithms in practice. First we consider the call-by-value higher-order language with state, RML. This can be viewed as a canonical restriction of Standard ML to ground-type references. The O-strict fragment of RML is the largest set of type sequents for which, in the game-semantic denotation, justification pointers from O-moves are always uniquely reconstructible from the underlying move sequence. The O-strict fragment is surprisingly expressive, including higher-order types and difficult examples from the literature. By representing strategies as Visibly Pushdown Automata (VPA) we show that observational equivalence of O-strict terms is decidable (and in fact is ExpTime-complete). We then consider extensions of the O-strict fragment. Adding general recursion or using most non-O-strict types leads to undecidability. However, a limited form of recursion can be added while still preserving decidability (although the full power of DPDA is required). Next we examine languages with non-local control. This involves adding call/cc to our language and is known to correspond to dropping the game-semantic bracketing condition. In the call-by-name game-semantic model of Idealized Algol (IA), in which answers cannot justify questions, the visibility condition still implies a form of weak bracketing. By making bracketing violations explicit we show that we can still model the entire third-order fragment using VPA. We have also implemented tools based on these algorithms. Our model checkers Homer and Hector perform equivalence checking for third-order IA and O-strict RML respectively. Homer uses a naive explicit state method whereas Hector takes advantage of on-the-fly model checking. Our tools perform well on small yet challenging examples. On negative instances, the on-the-fly approach allows Hector to outperform Homer. To improve their performance, we also consider using ideas from symbolic execution. We propose a representation for finite automata using transitions labelled with formulas and guards which aims to take advantage of the symmetries of the game-semantic model so that strategies can be represented compactly. We refer to this representation as Symbolically Executed Automata (SEA). Using SEA allows much larger data types to be handled but is not as effective on larger examples with small data types.

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark paradigm. The new heuristic’s novel feature is that it computes and stores a reduced amount of preprocessed information (in comparison to previous landmark-based algorithms) while enabling more informed search decisions. We demonstrate that domination of this heuristic over its predecessor depends on landmark selection and that, in general, the denser the landmark set, the better heuristic performs. Due to the reduced memory requirement, this new heuristic admits much denser landmark sets. We conduct experiments to characterize the impact that landmark configurations have on this new heuristic, demonstrating that centrality-based landmark selection has the best tradeoff between preprocessing and runtime. Using a developed graph library and static information from benchmark road map datasets, the algorithm is compared experimentally with previous landmark-based shortest path techniques in a fixed-memory environment to demonstrate a reduction in overall computational time and memory requirements. Experimental results are evaluated to detail the significance of landmark selection and density, the tradeoffs of performing preprocessing, and the practical use cases of the algorithm.

We investigate higher order asymptotic theory in nonparametric time series analysis. The aim of these techniques is to approximate the finite sample distribution of estimates and test statistics. This is specially relevant for smoothed nonparametric estimates in the presence of autocorrelation, which have slow rates of convergence so that inference rules based on first-order asymptotic approximations may not be very precise. First we review the literature on autocorrelation-robust inference and higher order asymptotics in time series. We evaluate the effect of the nonparametric estimation of the variance in the studentization of least squares estimates in linear regression models by means of asymptotic expansions. Then, we obtain an Edgeworth expansion for the distribution of nonparametric estimates of the spectral density and studentized sample mean. Only local smoothness conditions on the spectrum of the time series are assumed, so long range dependence behaviour in the series is allowed at remote frequencies, not necessary only at zero frequency but at possible cyclical and seasonal ones. The nonparametric methods described rely on a bandwidth or smoothing number. We propose a cross-validation algorithm for the choice of the optimal bandwidth, in a mean square sense, at a single point without restrictions on the spectral density at other frequencies. Then, we focus on the performance of the spectral density estimates around a singularity due to long range dependence and we obtain their asymptotic distribution in the Gaussian case. Semiparametric inference procedures about the long memory parameter based on these nonparametric estimates are justified under mild conditions on the distribution of the observed time series. Using a fixed average of periodogram ordinates, we also prove the consistency of the log-periodogram regression estimate of the memory parameter for linear but non-Gaussian time series.

This thesis uses the latest advances in measurement theory to validate teachers' assessment of higher order thinking. The study developed a measurement scale of higher order thinking skills that can be used to monitor student performance in higher order thinking and contribute to the quality of teacher assessments of student performance in higher order thinking. Traditionally this process would involve starting with defining the construct (higher order thinking); delineating it into its component parts; operationalising it by constructing items or tasks to assess the parts; administrating the tasks to students; and using the resuilts from the exercise to locate the task or component parts of the tasks onto the developmental continuum. What characterises this study is that the starting point was the understanding of the construct by a group of teachers who have been assessing higher order skills for a number of years in a practical environment.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Education and Professional Studies
Arts, Education and Law
Full Text

The relative scarcity of results that guarantee the existence of solutions for BVP on unbounded domains, contrasts with the high applicability on real problems of differential equations defined on the half-line or on the whole real line. It is this gap the main reason that led to this work. The differential equations studied vary from second order to higher orders and they can be discontinuous on time. Different types of boundary conditions will be discussed herein, for example, Sturm- Liouville, homoclinic, Lidstone and functional conditions. The non-compactness of the time interval and the possibility of study unbounded functions will require the redefinition of the admissible Banach spaces. In fact the space considered and the functional framework assumed define the set of admissible solutions for each problem under a main goal: the functions must remain bounded for the space and the norm in consideration. This is achieved by defining some weight functions (polynomial or exponential) in the space or assuming some asymptotic behavior. In addition to the existence, solutions will be localized in a strip. The lower and upper solutions method will play an important role, and combined with other tools like the one-sided Nagumo growth conditions, Green’s functions or Schauder’s fixed point theorem, provide the existence and location results for differential equations with various boundary conditions. Different applications to real phenomena will be presented, most of them translated into classical equations as Duffing, Bernoulli-Eulerv. Karman, Fisher-Kolmogorov, Swift-Hohenberg, Emden-Fowler or Falkner-Skan-type equations. All these applications have a common denominator: they are defined in unbounded intervals and the existing results in the literature are scarce or proven only numerically in discrete problems; RESUMO: Problemas de valor na fronteira de ordem superior em intervalos não limitados A relativa escassez de resultados que garantam a existência de soluções para problemas de valor na fronteira, em domínios ilimitados, contrasta com a alta aplicabilidade em problemas reais de equações diferenciais definidas na semi reta ou em toda a reta real. É esta lacuna o principal motivo que conduziu a este trabalho. As equações diferenciais estudadas variam da segunda ordem a ordens superiores e podem ser descontínuas no tempo. As condições de fronteira aqui analisadas são de diferentes tipos, nomeadamente, Sturm - Liouville, homoclínicas, Lidstone e condições funcionais. A não compacidade do intervalo de tempo e a possibilidade de estudar funções ilimitadas, exigirá a redefinição dos espaços de Banach admissíveis. Na verdade, o espaço considerado e o quadro funcional assumido define o conjunto de soluções admissíveis para cada problema sob um objetivo principal: as funções devem permanecer limitadas para o espaço e norma considerados. Isto é conseguido através da definição de algumas "funções de peso" (polinomiais ou exponenciais) no espaço considerado ou assumindo um comportamento assintótico. Além da existência, as soluções serão localizadas numa faixa. O método da sub e sobre-soluções irá desempenhar aqui um papel importante e, combinado com outras ferramentas como a condição unilateral de Nagumo, as funções de Green ou o teorema de ponto fixo de Schauder, fornecem a existência e localização de soluções para equações diferenciais com diversas condições de fronteira. Apresentam-se também diferentes aplicações a fenómenos reais, a maioria deles traduzidos para equações clássicas como as equações de Duffing, Bernoulli-Euler-v.Karman, Fisher-Kolmogorov, Swift - Hohenberg, Emden-Fowler ou ainda Falkner-Skan. Todas estas aplicações têm um denominador comum: são definidas em intervalos ilimitados e os resultados existentes na literatura são raros ou estão provados apenas numericamente em problemas discretos.

Le système de types de la logique d'ordre supérieur permet d'exclure certaines expressions indésirables telles que l'application d'un prédicat à lui-même. Cependant, il ne suffit pas pour vérifier des critères plus complexes comme l'absence de divisions par zéro. Cette thèse est consacrée à l’étude d’une extension de la logique d’ordre supérieur appelée sous-typage par prédicats (predicate subtyping), dont l'objet est de rendre l'attribution de types aussi expressive que l'attribution de prédicats. A partir d'un type A et d'un prédicat P(x) de domaine A, le sous-typage par prédicats permet de construire un sous-type de A, noté {x : A | P(x)}, dont les éléments sont les termes t de type A tels que P(t) est démontrable. Le sous-typage par prédicats est au coeur du système PVS.Ce travail présente la formalisation d'un système minimal incluant le sous-typage par prédicats, appelé PVS-Core, ainsi qu'un système de certificats vérifiables pour PVS-Core. Ce deuxième système, appelé PVS-Cert, repose sur l'introduction de termes de preuves et de coercions explicites. PVS-Core et PVS-Cert sont munis d'une notion de conversion correspondant respectivement à l'égalité modulo beta et à l'égalité modulo beta et effacement des coercions, choisi pour établir une correspondance simple entre les deux systèmes.La construction de PVS-Cert est semblable à celle des PTS (Pure Type Systems) avec paires dépendantes et PVS-Cert peut être muni de la notion de beta-sigma-réduction utilisée au coeur de ces systèmes. L'un des principaux théorèmes démontré dans ce travail est la normalisation forte de la réduction sous-jacente à la conversion et de la beta-sigma-réduction. Ce théorème permet d'une part de construire un algorithme de vérification du typage (et des preuves) pour PVS-Cert et d'autre part de démontrer un résultat d'élimination des coupures, utilisé à son tour pour prouver plusieurs propriétés importantes des deux systèmes étudiés. Par ailleurs, il est également démontré que PVS-Cert est une extension conservative du PTS lambda-HOL, et qu'en conséquence PVS-Core est une extension conservative de la logique d'ordre supérieur.Une deuxième partie présente le prototype d'une instrumentation de PVS pour produire des certificats de preuve. Une troisième et dernière partie est consacrée à l'étude de liens entre logique classique et constructive avec la définition d'une traduction par double négation minimale ainsi que la présentation d'un algorithme de constructivisation automatique des preuves
The type system of higher-order logic allows to exclude some unexpected expressions such as the application of a predicate to itself. However, it is not sufficient to verify more complex criteria such as the absence of divisions by zero. This thesis is dedicated to the study of an extension of higher-order logic, named predicate subtyping, whose purpose is to make the assignment of types as expressive as the assignment of predicates. Starting from a type A and a predicate P(x) of domain A, predicate subtyping allows to build a subtype of A, denoted {x : A | P(x)}, whose elements are the terms t of type A such that P(t) is provable. Predicate subtyping is at the heart of the proof system PVS.This work presents the formalization of a minimal system expressing predicate subtyping, named PVS-Core, as well as a system of verifiable certificates for PVS-Core. This second system, named PVS-Cert, is based on the introduction of proof terms and explicit coercions. PVS-Core and PVS-Cert are equipped with a notion of conversion corresponding respectively to equality modulo beta and to equality modulo beta and the erasure of coercions, chosen to establish a simple correspondence between the two systems.The construction of PVS-Cert is similar to that of PTSs (Pure Type Systems) with dependent pairs and PVS-Cert can be equipped with the notion of beta-sigma-reduction used at the core of these systems. One of the main theorems proved in this work is the strong normalization of both the reduction underlying the conversion and beta-sigma-reduction. This theorem allows, on the one hand, to build a type-checking (and proof-checking) algorithm for PVS-Cert and, on the other hand, to prove a cut elimination result, used in turn to prove important properties of the two studied systems. Furthermore, it is also proved that PVS-Cert is a conservative extension of the PTS lambda-HOL and that, as a consequence, PVS-Core is a conservative extension of higher-order logic.A second part presents the prototype of an instrumentation of PVS to generate proof certificates. A third and final part is dedicated to the study of links between classical and constructive logic, with the definition of a minimal double-negation translation as well as the presentation of an automated proof constructivization algorithm

Hadronic collider experiments have played a major role in particle physics phenomenology over the last few decades. Data recorded at the Tevatron at Fermilab is still of interest, and its successor, the Large Hadron Collider (LHC) at CERN, has recently announced the discovery of a particle consistent with the Standard Model Higgs boson. Hadronic colliders look set to guide the field for the next fifteen years or more, with the discovery of more particles anticipated. The discovery and detailed study of new particles relies crucially on the availability of high-precision theoretical predictions for both the signal and background processes. This requires observables to be calculated to next-to-leading order (NLO) in perturbative quantum chromodynamics (QCD). Many hadroproduction processes of interest contain multiple particles in the final state. Until recently, this caused a bottleneck in NLO QCD calculations, due to the difficulty in calculating one-loop corrections to processes involving three or more final state particles. Spectacular developments in on-shell methods over the last six years have made these calculations feasible, allowing highly accurate predictions for final state observables at the Tevatron and LHC. A particular realisation of on-shell methods, generalised unitarity, is used to compute the NLO QCD cross-sections and distributions for two processes: the hadroproduction of W⁺ W^-jj, and the hadroproduction of W⁺ W^-jj. The NLO corrections to both processes serve to reduce the scale dependence of the results significantly, while having a moderate effect on the central scale choice cross-sections, and leaving the shapes of the kinematic distributions mostly unchanged. Additionally, the gluon fusion contribution to the next-to-next-to-leading order (NNLO) QCD corrections to W⁺ W^-j productions are studied. These contributions are found to be highly depen- dent on the kinematic cuts used. For cuts used in Higgs searches, the gluon fusion effect can be as large as the NLO scale uncertainty, and should not be neglected. All of the higher-order QCD corrections increase the accuracy and reliability of the theoretical predictions at hadronic colliders.