<p>In this dissertation, we emphasize productiveness not just undecidability since pro- ductiveness implies constructive incompleteness. Analogues of Rice?s Theorem for different classes of languages are investigated, refined and generalized. In particular, several sufficient but general conditions are presented for predicates to be as hard as some widely discussed predicates such as ?= ?? and ?= {0,1}??. These conditions provide several general methods for proving complexity/productiveness results and apply to a large number of simple and natural predicates. As the first step in apply- ing these general methods, we investigate the complexity/productiveness of the pred- icates ?= ??, ?= {0,1}?? and other predicates that can be useful sources of many- one reductions for different classes of languages. Then we use very efficient many- one reductions of these basic source predicates to prove many new non-polynomial complexity lower bounds and productiveness results. Moreover, we study the com- plexity/productiveness of predicates for easily recognizable subsets of instances with important semantic properties. Because of the efficiency of our reductions, intuitively these reductions can preserve many levels of complexity. We apply our general methods to pattern languages [1] and multi-pattern lan- guages [2]. Interrelations between multi-pattern languages (or pattern languages) and standard classes of languages such as context-free languages and regular languages are studied. A way to study the descriptional complexity of standard language descriptors (for examples, context-free grammars and regular expressions) and multi-patterns is illustrated. We apply our general methods to several generalizations of regular ex- pressions. A productiveness result for the predicate ?= {0,1}?? is established for synchronized regular expressions [3]. Because of this, many new productiveness re- sults for synchronized regular expressions follow easily. We also apply our general methods to several classes of Lindenmayer systems [4] and of cellular automata [5]. A way of studying the complexity/productiveness of the 0Lness problem is developed and many new results follow from it. For real time one-way cellular automata, we observe that the predicates ?= ?? and ?= {0,1}?? are both productive. Because vi of this, many more general results are presented. For two-way cellular automata, we prove a strong meta-theorem and give a complete characterization for testing containment of any fixed two-way cellular automaton language. Finally, we generalize our methods and apply them to the theory of functions of real variables. In rings, the equivalence to identically 0 function problem which is an analogue of ?= ?? is studied. We show that the equivalence to identically 0 function problem for some classes of elementary functions is productive for different domains including open and closed bounded intervals of real numbers. Two initial results for real fields are also presented.

<p> Relative motion is an ecological mechanism with the power to change the stability and longevity of populations and predict large scale movement patterns in highly mobile species. This dissertation introduces relative motion as an ecological mechanism using simulations and experiments at varying levels of spatial complexity. Chapters 2 and 3 describe the interactions between population movement and one-dimensional habitat movement, while Chapters 4 and 5 focus on the interactions between individual movement and three-dimensional habitat movement. Chapters 2 and 4 lay out my model justification, model development, and simulation results, while the remaining two chapters describe case studies competing those models with data. In Chapter 2, I simulate populations chasing moving habitat using stochastic spatial spread models. Results from these simulations show that populations lose symmetry when the habitat begins to move and suggest that loss of symmetry increases extinction risk. Results also show that assisted migration can restore some of that lost symmetry, but the success of assisted migration is sensitive to the transplant location and habitat speed. In Chapter 3, I build on the simulations presented in Chapter 2 by investigating assisted migration as a method of restoring symmetry using <i> Tribolium</i> microcosm experiments. Experimental results show that assisted migration both restored symmetry to the moving populations under fast-moving habitat conditions and significantly reduced extinction risk compared to the controls. Chapter 4 describes a 3-dimensional Geographic Information System (GIS) to track multiple sources of relative motion in the environment at once, using rigid body mathematics to move individual components in their own direction. In Chapter 5, I apply this GIS to deconstruct the migratory paths of 22 Greater shearwater (<i>Puffinus gravis</i>) migrants and rank the relative contributions of solar, wind, temperature, humidity, and surface cues to the figure-8 shaped migratory paths observed in this species.</p>

This research concerns information systems and information systems development. The thesis describes an approach to information systems development called Multiview. This is a methodology which seeks to combine the strengths of a number of different, existing approaches in a coherent manner. Many of these approaches are radically different in terms of concepts, philosophy, assumptions, methods, techniques and tools. Three case studies are described presenting Multiview 'in action'. The first is used mainly to expose the strengths and weaknesses of an early version of the approach discussed in the thesis. Tools and techniques are described in the thesis which aim to strengthen the approach. Two further case studies are presented to illustrate the use of this second version of Multiview. This is not put forward as an 'ideal methodology' and the case studies expose some of the difficulties and practical problems of information systems work and the use of the methodology. A more contingency based approach to information systems development is advocated using Multiview as a framework rather than a prescriptive tool. Each information systems project and the use of the framework is unique, contingent on the particular problem situation. The skills of different analysts, the backgrounds of users and the situations in which they are constrained to work have always to be taken into account in any project. The realities of the situation will cause departure from the 'ideal methodology' in order to allow for the exigencies of the real world. Multiview can therefore be said to be an approach used to explore the application area in order to develop an information system.

In the last twenty or so years the results of theory and experiment have produced much information on the characteristics of gas-surface interactions relevant to a satellite in hyperthermal free-molecular flow. This thesis contains reviews of the rarefied gas dynamics applicable to satellites and has attempted to compare existing models of gas-surface interaction with contemporary knowledge of such systems. It is shown that a more natural approach would be to characterise the gas-surface interaction using the normal and tangential momentum accommodation coefficients, igma' and igma respectively, specifically in the form igma = constant , igma' = igma'0 -igma'1sec i where i is the angle subtended between the incident flow and the surface normal and igma,igma'0 and igma'1 are constants. Adopting these relationships, the effects of atmospheric lift on inclination, i, and atmospheric drag on the semi-major axis, a, and eccentricity, e, have been investigated. Applications to ANS-1 (1974-70A) show that the observed perturbation in i can be ascribed primarily to non-zero igma'1 whilst perturbations in a and e produce constraint equations between the three parameters. The numerical results seem to imply that a good theoretical orbit is achieved despite a much lower drag coefficient than anticipated by earlier theories.

Image segmentation is one of the most computationally intensive operations in image processing and computer vision. This is because a large volume of data is involved and many different features have to be extracted from the image data. This thesis is concerned with the investigation of practical issues related to the implementation of several classes of image segmentation algorithms on parallel architectures. The Transputer is used as the basic building block of hardware architectures and Occam is used as the programming language. The segmentation methods chosen for implementation are convolution, for edge-based segmentation; the Split and Merge algorithm for segmenting non-textured regions; and the Granlund method for segmentation of textured images. Three different convolution methods have been implemented. The direct method of convolution, carried out in the spatial domain, uses the array architecture. The other two methods, based on convolution in the frequency domain, require the use of the two-dimensional Fourier transform. Parallel implementations of two different Fast Fourier Transform algorithms have been developed, incorporating original solutions. For the Row-Column method the array architecture has been adopted, and for the Vector-Radix method, the pyramid architecture. The texture segmentation algorithm, for which a system-level design is given, demonstrates a further application of the Vector-Radix Fourier transform. A novel concurrent version of the quad-tree based Split and Merge algorithm has been implemented on the pyramid architecture. The performance of the developed parallel implementations is analysed. Many of the obtained speed-up and efficiency measures show values close to their respective theoretical maxima. Where appropriate comparisons are drawn between different implementations. The thesis concludes with comments on general issues related to the use of the Transputer system as a development tool for image processing applications; and on the issues related to the engineering of concurrent image processing applications.

This thesis is concerned with exact solutions of Einstein's field equations of general relativity, in particular, when the source of the gravitational field is a perfect fluid with a purely electric Weyl tensor. General relativity, cosmology and computer algebra are discussed briefly. A mathematical introduction to Riemannian geometry and the tetrad formalism is then given. This is followed by a review of some previous results and known solutions concerning purely electric perfect fluids. In addition, some orthonormal and null tetrad equations of the Ricci and Bianchi identities are displayed in a form suitable for investigating these space-times. Conformally flat perfect fluids are characterised by the vanishing of the Weyl tensor and form a sub-class of the purely electric fields in which all solutions are known (Stephani 1967). The number of Killing vectors in these space-times is investigated and results presented for the non-expanding space-times. The existence of stationary fields that may also admit 0, 1 or 3 spacelike Killing vectors is demonstrated. Shear-free fluids in the class under consideration are shown to be either non-expanding or irrotational (Collins 1984) using both orthonormal and null tetrads. A discrepancy between Collins (1984) and Wolf (1986) is resolved by explicitly solving the field equations to prove that the only purely electric, shear-free, geodesic but rotating perfect fluid is the Godel (1949) solution. The irrotational fluids with shear are then studied and solutions due to Szafron (1977) and Allnutt (1982) are characterised. The metric is simplified in several cases where new solutions may be found. The geodesic space-times in this class and all Bianchi type 1 perfect fluid metrics are shown to have a metric expressible in a diagonal form. The position of spherically symmetric and Bianchi type 1 space-times in relation to the general case is also illustrated.

<p> We start by introducing <i>avoidance coupling</i> of Markov chains, with an overview of existing results. We then introduce and motivate a new notion, <i>uniform coupling.</i> We show that the only Markovian avoidance coupling on a cycle is of this type, and that uniform avoidance coupling of simple random walks is impossible on trees, and prove that it is possible on several classes of graphs. We also derive a condition on the vertex neighborhoods in a graph equivalent to that graph admitting a uniform avoidance coupling of simple random walks, and an algorithm that tests this with run time polynomial in the number of vertices. We then discuss a conjecture that no Markovian avoidance coupling can be possible on a tree and propose how a proof might proceed. </p><p> In the second half of this work, we talk about the design of online communication systems that aim to guarantee anonymity for their users. A popular paradigm is <i>k</i>-anonymity. We notice that the scarcity of a typical social relation makes <i>k</i>-anonymity vulnerable to traffic analysis, and propose a way to use this scarcity to reduce the efficiency cost to exactly the amount of cover traffic we might need. Then we use Bregman's theorem to show that for a given infrastructure cost, modelled by the number of edges in a bipartite graph, <i>k</i>-anonymity offers the highest number of possible perfect matchings between users and observed behaviors.</p>

<p> The purpose of vision is to find behaviorally relevant structure in the ever-flowing chaos of sensory input. In the primate, this goal is achieved by a hierarchy of cortical areas that extract increasingly complex forms of information from the light arriving at the retina. Despite success characterizing the early stages of this pathway &mdash; the retina, the lateral geniculate nucleus, and primary visual cortex (V1) &mdash; we have a poor understanding of how transformations in later stages yield selectivity for the complex shapes and objects that primates readily recognize.</p><p> According to a classical, constructionist view, the later stages of the visual system assemble elementary inputs &mdash; like the oriented features encoded by V1 &mdash; into larger and more complex combinations, capturing the structural relationships that determine the visual world. But this approach has stumbled on the enigmatic second visual area, V2, whose neurons defy our intuitions about how to begin segmenting scenes and encoding the shapes of objects.</p><p> In this thesis we develop a framework for the study of intermediate visual processing in the primate, focused on computation and representation in area V2. Rather than try to predict the responses of visual neurons to arbitrary inputs, we test hypotheses about their function by generating targeted experimental stimuli. The stimuli we use reflect the messy statistical reality of natural images, rather than intuitions about object construction. We identify novel responses properties in macaque and human V2 that robustly differentiates it from V1. We propose mechanistic explanations for these properties by contextualizing them among existing models of hierarchical computation. And we link these properties to several perceptual capabilities -- and limits -- that appear to depend specifically on processing in V2, and imply striking consequences for everyday vision.</p>

Thesis (Ph. D.)--Syracuse University, 2009. / "Publication number:; AAT 3381575."

<p> In this thesis we prove intractability results for several well studied problems in combinatorial optimization. </p><p> <b>Closest Vector Problem with Pre-processing (CVPP):</b> We show that the pre-processing version of the well known C<p style="font-variant: small-caps">LOSEST</p> V<p style="font-variant: small-caps">ECTOR</p> P<p style="font-variant: small-caps">ROBLEM</p> is hard to approximate to an almost polynomial factor unless NP is in quasi polynomial time. The approximability of CVPP is closely related to the security of lattice based cryptosystems. </p><p> <b>Pricing Loss Leaders:</b> We show hardness of approximation results for the problem of maximizing profit from buyers with <i>single minded valuations</i> where each buyer is interested in bundles of at most <i>k</i> items, and the items are allowed to have negative prices ("Loss Leaders"). For <i>k</i> = 2, we show that assuming the U<p style="font-variant: small-caps">NIQUE</p> G<p style="font-variant: small-caps">AMES</p> C<p style="font-variant: small-caps">ONJECTURE</p>, it is hard to approximate the profit to any constant factor. For <i> k</i> &ge; 2, we show the same result assuming <i>P</i> &ne; <i> NP</i>. </p><p> <b>Integrality gaps:</b> We show Semi-Definite Programming (SDP) integrality gaps for U<p style="font-variant: small-caps">NIQUE</p> G<p style="font-variant: small-caps">AMES</p> and 2-to-1 G<p style="font-variant: small-caps">AMES</p>. Inapproximability results for these problems imply inapproximability results for many fundamental optimization problems. For the first problem, we show "approximate" integrality gaps for super constant rounds of the powerful Lasserre hierarchy. For the second problem we show integrality gaps for the basic SDP relaxation with perfect completeness.</p>