A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders

We give an explicit and easy-to-verify characterization for subsets in finite total orders (infinitely many of them in general) to be uniformly definable by a first-order formula. From this characterization we derive immediately that Beth's definability theorem does not hold in any class of finite total orders, as well as that McColm's first conjecture is true for all classes of finite total orders. Another consequence is a natural 0-1 law for definable subsets on finite total orders expressed as a statement about the possible densities of first-order definable subsets.

Validating Arbitrarily Large Network Protocol Compositions with Finite Computation

Formal tools like finite-state model checkers have proven useful in verifying the correctness of systems of bounded size and for hardening single system components against arbitrary inputs. However, conventional applications of these techniques are not well suited to characterizing emergent behaviors of large compositions of processes. In this paper, we present a methodology by which arbitrarily large compositions of components can, if sufficient conditions are proven concerning properties of small compositions, be modeled and completely verified by performing formal verifications upon only a finite set of compositions. The sufficient conditions take the form of reductions, which are claims that particular sequences of components will be causally indistinguishable from other shorter sequences of components. We show how this methodology can be applied to a variety of network protocol applications, including two features of the HTTP protocol, a simple active networking applet, and a proposed web cache consistency algorithm. We also doing discuss its applicability to framing protocol design goals and to representing systems which employ non-model-checking verification methodologies. Finally, we briefly discuss how we hope to broaden this methodology to more general topological compositions of network applications.

Principality and Decidable Type Inference for Finite-Rank Intersection Types

Principality of typings is the property that for each typable term, there is a typing from which all other typings are obtained via some set of operations. Type inference is the problem of finding a typing for a given term, if possible. We define an intersection type system which has principal typings and types exactly the strongly normalizable λ-terms. More interestingly, every finite-rank restriction of this system (using Leivant's first notion of rank) has principal typings and also has decidable type inference. This is in contrast to System F where the finite rank restriction for every finite rank at 3 and above has neither principal typings nor decidable type inference. This is also in contrast to earlier presentations of intersection types where the status of these properties is not known for the finite-rank restrictions at 3 and above.Furthermore, the notion of principal typings for our system involves only one operation, substitution, rather than several operations (not all substitution-based) as in earlier presentations of principality for intersection types (of unrestricted rank). A unification-based type inference algorithm is presented using a new form of unification, β-unification.

Applications of finite element computer modelling and thermal infrared remote sensing to the study of geothermal anomalies

Buried heat sources can be investigated by examining thermal infrared images and comparing these with the results of theoretical models which predict the thermal anomaly a given heat source may generate. Key factors influencing surface temperature include the geometry and temperature of the heat source, the surface meteorological environment, and the thermal conductivity and anisotropy of the rock. In general, a geothermal heat flux of greater than 2% of solar insolation is required to produce a detectable thermal anomaly in a thermal infrared image. A heat source of, for example, 2-300K greater than the average surface temperature must be a t depth shallower than 50m for the detection of the anomaly in a thermal infrared image, for typical terrestrial conditions. Atmospheric factors are of critical importance. While the mean atmospheric temperature has little significance, the convection is a dominant factor, and can act to swamp the thermal signature entirely. Given a steady state heat source that produces a detectable thermal anomaly, it is possible to loosely constrain the physical properties of the heat source and surrounding rock, using the surface thermal anomaly as a basis. The success of this technique is highly dependent on the degree to which the physical properties of the host rock are known. Important parameters include the surface thermal properties and thermal conductivity of the rock. Modelling of transient thermal situations was carried out, to assess the effect of time dependant thermal fluxes. One-dimensional finite element models can be readily and accurately applied to the investigation of diurnal heat flow, as with thermal inertia models. Diurnal thermal models of environments on Earth, the Moon and Mars were carried out using finite elements and found to be consistent with published measurements. The heat flow from an injection of hot lava into a near surface lava tube was considered. While this approach was useful for study, and long term monitoring in inhospitable areas, it was found to have little hazard warning utility, as the time taken for the thermal energy to propagate to the surface in dry rock (several months) in very long. The resolution of the thermal infrared imaging system is an important factor. Presently available satellite based systems such as Landsat (resolution of 120m) are inadequate for detailed study of geothermal anomalies. Airborne systems, such as TIMS (variable resolution of 3-6m) are much more useful for discriminating small buried heat sources. Planned improvements in the resolution of satellite based systems will broaden the potential for application of the techniques developed in this thesis. It is important to note, however, that adequate spatial resolution is a necessary but not sufficient condition for successful application of these techniques.

Uniformly convergent finite element and finite difference methods for singularly perturbed ordinary differential equations

This thesis is concerned with uniformly convergent finite element and finite difference methods for numerically solving singularly perturbed two-point boundary value problems. We examine the following four problems: (i) high order problem of reaction-diffusion type; (ii) high order problem of convection-diffusion type; (iii) second order interior turning point problem; (iv) semilinear reaction-diffusion problem. Firstly, we consider high order problems of reaction-diffusion type and convection-diffusion type. Under suitable hypotheses, the coercivity of the associated bilinear forms is proved and representation results for the solutions of such problems are given. It is shown that, on an equidistant mesh, polynomial schemes cannot achieve a high order of convergence which is uniform in the perturbation parameter. Piecewise polynomial Galerkin finite element methods are then constructed on a Shishkin mesh. High order convergence results, which are uniform in the perturbation parameter, are obtained in various norms. Secondly, we investigate linear second order problems with interior turning points. Piecewise linear Galerkin finite element methods are generated on various piecewise equidistant meshes designed for such problems. These methods are shown to be convergent, uniformly in the singular perturbation parameter, in a weighted energy norm and the usual L2 norm. Finally, we deal with a semilinear reaction-diffusion problem. Asymptotic properties of solutions to this problem are discussed and analysed. Two simple finite difference schemes on Shishkin meshes are applied to the problem. They are proved to be uniformly convergent of second order and fourth order respectively. Existence and uniqueness of a solution to both schemes are investigated. Numerical results for the above methods are presented.

Uniformly convergent finite element methods for singularly perturbed parabolic partial differential equations

This thesis is concerned with uniformly convergent finite element methods for numerically solving singularly perturbed parabolic partial differential equations in one space variable. First, we use Petrov-Galerkin finite element methods to generate three schemes for such problems, each of these schemes uses exponentially fitted elements in space. Two of them are lumped and the other is non-lumped. On meshes which are either arbitrary or slightly restricted, we derive global energy norm and L2 norm error bounds, uniformly in the diffusion parameter. Under some reasonable global assumptions together with realistic local assumptions on the solution and its derivatives, we prove that these exponentially fitted schemes are locally uniformly convergent, with order one, in a discrete L∞norm both outside and inside the boundary layer. We next analyse a streamline diffusion scheme on a Shishkin mesh for a model singularly perturbed parabolic partial differential equation. The method with piecewise linear space-time elements is shown, under reasonable assumptions on the solution, to be convergent, independently of the diffusion parameter, with a pointwise accuracy of almost order 5/4 outside layers and almost order 3/4 inside the boundary layer. Numerical results for the above schemes are presented. Finally, we examine a cell vertex finite volume method which is applied to a model time-dependent convection-diffusion problem. Local errors away from all layers are obtained in the l2 seminorm by using techniques from finite element analysis.

Flat surfaces of finite type in the 3-sphere

We introduce the notion of flat surfaces of finite type in the 3- sphere, give the algebro-geometric description in terms of spectral curves and polynomial Killing fields, and show that finite type flat surfaces generated by curves on S2 with periodic curvature functions are dense in the space of all flat surfaces generated by curves on S2 with periodic curvature functions.

The multiple reality: A critical study on Alfred Schutz’s sociology of the finite provinces of meaning

This work is a critical introduction to Alfred Schutz’s sociology of the multiple reality and an enterprise that seeks to reassess and reconstruct the Schutzian project. In the first part of the study, I inquire into Schutz’s biographical context that surrounds the germination of this conception and I analyse the main texts of Schutz where he has dealt directly with ‘finite provinces of meaning.’ On the basis of this analysis, I suggest and discuss, in Part II, several solutions to the shortcomings of the theoretical system that Schutz drew upon the sociological problem of multiple reality. Specifically, I discuss problems related to the structure, the dynamics, and the interrelationing of finite provinces of meaning as well as the way they relate to the questions of narrativity, experience, space, time, and identity.

Finite mixture distributions, sequential likelihood and the EM algorithm

A popular way to account for unobserved heterogeneity is to assume that the data are drawn from a finite mixture distribution. A barrier to using finite mixture models is that parameters that could previously be estimated in stages must now be estimated jointly: using mixture distributions destroys any additive separability of the log-likelihood function. We show, however, that an extension of the EM algorithm reintroduces additive separability, thus allowing one to estimate parameters sequentially during each maximization step. In establishing this result, we develop a broad class of estimators for mixture models. Returning to the likelihood problem, we show that, relative to full information maximum likelihood, our sequential estimator can generate large computational savings with little loss of efficiency.

Finite size effects in the presence of a chemical potential: A study in the classical nonlinear O(2) sigma model

In the presence of a chemical potential, the physics of level crossings leads to singularities at zero temperature, even when the spatial volume is finite. These singularities are smoothed out at a finite temperature but leave behind nontrivial finite size effects which must be understood in order to extract thermodynamic quantities using Monte Carlo methods, particularly close to critical points. We illustrate some of these issues using the classical nonlinear O(2) sigma model with a coupling β and chemical potential μ on a 2+1-dimensional Euclidean lattice. In the conventional formulation this model suffers from a sign problem at nonzero chemical potential and hence cannot be studied with the Wolff cluster algorithm. However, when formulated in terms of the worldline of particles, the sign problem is absent, and the model can be studied efficiently with the "worm algorithm." Using this method we study the finite size effects that arise due to the chemical potential and develop an effective quantum mechanical approach to capture the effects. As a side result we obtain energy levels of up to four particles as a function of the box size and uncover a part of the phase diagram in the (β,μ) plane. © 2010 The American Physical Society.

Stable isotope ratios indicate diet and habitat use in New World monkeys.

This paper demonstrates the use of stable isotope ratios of carbon and nitrogen in animal tissue for indicating aspects of species behavioral strategy. We analyzed hair from individuals representing four species of New World monkeys (Alouatta palliata, the mantled howler; Ateles geoffroyi, the spider monkey; Cebus capucinus, the capuchin; and Brachyteles arachnoides, the woolly-spider monkey or muriqui) for delta 13C and delta 15N using previously developed methods. There are no significant differences in either carbon or nitrogen ratios between sexes, sampling year, or year of analysis. Seasonal differences in delta 13C reached a low level of significance but do not affect general patterns. Variation within species was similar to that recorded previously within single individuals. The omega 13C data show a bimodal distribution with significant difference between the means. The two monkey populations living in an evergreen forest were similar to each other and different from the other two monkey populations that inhabited dry, deciduous forests. This bimodal distribution is independent of any particular species' diet and reflects the level of leaf cover in the two types of forest. The delta 15N data display three significantly different modes. The omnivorous capuchins were most positive reflecting a trophic level offset. The spider monkeys and the muriquis were similar to one another and significantly more positive than the howlers. This distribution among totally herbivorous species correlates with the ingestion of legumes by the howler monkey population. In combination, these data indicate that museum-curated primate material can be analyzed to yield information on forest cover and diet in populations and species lacking behavioral data.

Modeling the Effects of Habitat Fragmentation on the Movements of the Mongolian Gazelle in the Eastern Mongolian Steppe

The Mongolian gazelle, Procapra gutturosa, resides in the immense and dynamic ecosystem of the Eastern Mongolian Steppe. The Mongolian Steppe ecosystem dynamics, including vegetation availability, change rapidly and dramatically due to unpredictable precipitation patterns. The Mongolian gazelle has adapted to this unpredictable vegetation availability by making long range nomadic movements. However, predicting these movements is challenging and requires a complex model. An accurate model of gazelle movements is needed, as rampant habitat fragmentation due to human development projects - which inhibit gazelles from obtaining essential resources - increasingly threaten this nomadic species. We created a novel model using an Individual-based Neural Network Genetic Algorithm (ING) to predict how habitat fragmentation affects animal movement, using the Mongolian Steppe as a model ecosystem. We used Global Positioning System (GPS) collar data from real gazelles to “train” our model to emulate characteristic patterns of Mongolian gazelle movement behavior. These patterns are: preferred vegetation resources (NDVI), displacement over certain time lags, and proximity to human areas. With this trained model, we then explored how potential scenarios of habitat fragmentation may affect gazelle movement. This model can be used to predict how fragmentation of the Mongolian Steppe may affect the Mongolian gazelle. In addition, this model is novel in that it can be applied to other ecological scenarios, since we designed it in modules that are easily interchanged.

Finite groups and geometries: a view on the present state and on the future

The model: groups of Lie-Chevalley type and buildingsThis paper is not the presentation of a completed theory but rather a report on a search progressing as in the natural sciences in order to better understand the relationship between groups and incidence geometry, in some future sought-after theory Τ. The search is based on assumptions and on wishes some of which are time-dependent, variations being forced, in particular, by the search itself.A major historical reference for this subject is, needless to say, Klein's Erlangen Programme. Klein's views were raised to a powerful theory thanks to the geometric interpretation of the simple Lie groups due to Tits (see for instance), particularly his theory of buildings and of groups with a BN-pair (or Tits systems). Let us briefly recall some striking features of this.Let G be a group of Lie-Chevalley type of rank r, denned over GF(q), q = pn, p prime. Let Xr denote the Dynkin diagram of G. To these data corresponds a unique thick building B(G) of rank r over the Coxeter diagram Xr (assuming we forget arrows provided by the Dynkin diagram). It turns out that B(G) can be constructed in a uniform way for all G, from a fixed p-Sylow subgroup U of G, its normalizer NG(U) and the r maximal subgroups of G containing NG(U).

A natural extension of the conventional finite volume method into polygonal unstructured meshes for CFD application.

A new general cell-centered solution procedure based upon the conventional control or finite volume (CV or FV) approach has been developed for numerical heat transfer and fluid flow which encompasses both structured and unstructured meshes for any kind of mixed polygon cell. Unlike conventional FV methods for structured and block structured meshes and both FV and FE methods for unstructured meshes, the irregular control volume (ICV) method does not require the shape of the element or cell to be predefined because it simply exploits the concept of fluxes across cell faces. That is, the ICV method enables meshes employing mixtures of triangular, quadrilateral, and any other higher order polygonal cells to be exploited using a single solution procedure. The ICV approach otherwise preserves all the desirable features of conventional FV procedures for a structured mesh; in the current implementation, collocation of variables at cell centers is used with a Rhie and Chow interpolation (to suppress pressure oscillation in the flow field) in the context of the SIMPLE pressure correction solution procedure. In fact all other FV structured mesh-based methods may be perceived as a subset of the ICV formulation. The new ICV formulation is benchmarked using two standard computational fluid dynamics (CFD) problems i.e., the moving lid cavity and the natural convection driven cavity. Both cases were solved with a variety of structured and unstructured meshes, the latter exploiting mixed polygonal cell meshes. The polygonal mesh experiments show a higher degree of accuracy for equivalent meshes (in nodal density terms) using triangular or quadrilateral cells; these results may be interpreted in a manner similar to the CUPID scheme used in structured meshes for reducing numerical diffusion for flows with changing direction.

Monotone scheme and boundary conditions for finite volume simulation of magnetohydrodynamic internal flows at high Hartmann number

A monotone scheme for finite volume simulation of magnetohydrodynamic internal flows at high Hartmann number is presented. The numerical stability is analysed with respect to the electromagnetic force. Standard central finite differences applied to finite volumes can only be numerically stable if the vector products involved in this force are computed with a scheme using a fully staggered grid. The electromagnetic quantities (electric currents and electric potential) must be shifted by half the grid size from the mechanical ones (velocity and pressure). An integral treatment of the boundary layers is used in conjunction with boundary conditions for electrically conducting walls. The simulations are performed with inhomogeneous electrical conductivities of the walls and reach high Hartmann numbers in three-dimensional simulations, even though a non-adaptive grid is used.