51 |
Intersection types and higer-order model checkingRamsay, Steven J. January 2014 (has links)
Higher-order recursion schemes are systems of equations that are used to define finite and infinite labelled trees. Since, as Ong has shown, the trees defined have a decidable monadic second order theory, recursion schemes have drawn the attention of research in program verification, where they sit naturally as a higher-order, functional analogue of Boolean programs. Driven by applications, fragments have been studied, algorithms developed and extensions proposed; the emerging theme is called higher-order model checking. Kobayashi has pioneered an approach to higher-order model checking using intersection types, from which many recent advances have followed. The key is a characterisation of model checking as a problem of intersection type assignment. This dissertation contributes to both the theory and practice of the intersection type approach. A new, fixed-parameter polynomial-time decision procedure is described for the alternating trivial automaton fragment of higher-order model checking. The algorithm uses a novel, type-directed form of abstraction refinement, in which behaviours of the scheme are distinguished according to the intersection types that they inhabit. Furthermore, by using types to reason about acceptance and rejection simultaneously, the algorithm is able to converge on a solution from two sides. An implementation, Preface, and an extensive body of evidence demonstrate empirically that the algorithm scales well to schemes of several thousand rules. A comparison with other tools on benchmarks derived from current practice and the related literature puts it well beyond the state-of-the-art. A generalisation of the intersection type approach is presented in which higher-order model checking is seen as an instance of exact abstract interpretation. Intersection type assignment is used to characterise a general class of safety checking problems, defined independently of any particular representation (such as automata) for a class of recursion schemes built over arbitrary constants. Decidability of any problem in the class is an immediate corollary. Moreover, the work looks beyond whole-program verification, the traditional territory of model checking, by giving a natural treatment of higher-type properties, which are sets of functions.
|
52 |
DIRECT PRODUCTS AND THE INTERSECTION MAP OF CERTAIN CLASSES OF FINITE GROUPSChifman, Julia 01 January 2009 (has links)
The main goal of this work is to examine classes of finite groups in which normality, permutability and Sylow-permutability are transitive relations. These classes of groups are called T , PT and PST , respectively. The main focus is on direct products of T , PT and PST groups and the behavior of a collection of cyclic normal, permutable and Sylow-permutable subgroups under the intersection map. In general, a direct product of finitely many groups from one of these classes does not belong to the same class, unless the orders of the direct factors are relatively prime. Examples suggest that for solvable groups it is not required to have relatively prime orders to stay in the class. In addition, the concept of normal, permutable and S-permutable cyclic sensitivity is tied with that of Tc, PTc and PSTc groups, in which cyclic subnormal subgroups are normal, permutable or Sylow-permutable. In the process another way of looking at the Dedekind, Iwasawa and nilpotent groups is provided as well as possible interplay between direct products and the intersection map is observed.
|
53 |
On the configuration of arrays of floating wave energy convertersChild, Benjamin Frederick Martin January 2011 (has links)
In this thesis, certain issues relating to a number of wave energy absorbers operating in the same vicinity are investigated. Specifically, arrangements of the devices within such an array are sought, such that beneficial hydrodynamic interference between members is exploited and unwanted effects mitigated. Arrays of `point absorber' devices as well as converters with multiple closely spaced floats are modelled and a frequency domain hydrodynamic solution derived. This is implemented as efficient computer code, capable of producing the full linear wave theory solution to any desired degree of accuracy. Furthermore, the results are verified against output from the boundary element code WAMIT. Initially, detailed analysis of an isolated absorber is conducted, with motion responses, forces, power output and velocity potentials at the free surface computed for a range of different device specifications. Elementary examples of arrays are then used to demonstrate the influence of factors such as device separation, wave heading angle, number of devices and array configuration upon collective performance. Subsequently, the power output from an array of five devices is optimised with respect to its layout, using two different routines. The first is a new heuristic approach, named the Parabolic Intersection (PI) method, that efficiently creates array con figurations using only basic computations. The second is a Genetic Algorithm (GA) with a novel `crossover' operator. Each method is applied to maximise the output at a given regular wave frequency and direction under two different power take-off regimes and also to minimise power in a third, cautionary example. The resulting arrays are then analysed and the optimisation procedures themselves evaluated. Finally, the effects of irregular seas on array interactions are investigated. The configurations that were optimised for regular wave climates are assessed in a range of irregular sea-states. The GA is then used once more to create optimal array layouts for each of these seas. The characteristics of the arrays are subsequently examined and the influence of certain spectral parameters on the optimal solutions considered. The optimisation procedures were both found to be effective, with the GA marginally outperforming the PI method in all cases. Significant positive and negative modifications to the power output were observed in the arrays optimised in regular waves, although the effects weakened when the same arrays were subjected to irregular sea-states. However, arrays optimised specifically in irregular seas exhibited differences in net power output equivalent to over half that produced from the same number of devices in isolation.
|
54 |
Daily Traffic Flow Pattern Recognition by Spectral ClusteringAven, Matthew 01 January 2017 (has links)
This paper explores the potential applications of existing spectral clustering algorithms to real life problems through experiments on existing road traffic data. The analysis begins with an overview of previous unsupervised machine learning techniques and constructs an effective spectral clustering algorithm that demonstrates the analytical power of the method. The paper focuses on the spectral embedding method’s ability to project non-linearly separable, high dimensional data into a more manageable space that allows for accurate clustering. The key step in this method involves solving a normalized eigenvector problem in order to construct an optimal representation of the original data.
While this step greatly enhances our ability to analyze the relationships between data points and identify the natural clusters within the original dataset, it is difficult to comprehend the eigenvalue representation of the data in terms of the original input variables. The later sections of this paper will explore how the careful framing of questions with respect to available data can help researchers extract tangible decision driving results from real world data through spectral clustering analysis.
|
55 |
Théorème de Kunneth en homologie de MorseFrankland, Martin January 2005 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
|
56 |
The Degree Sequence Problem for 3-HypergraphsZou, Yangsheng 13 April 2016 (has links)
Currently the degree sequence problem for 3-hypergraphs is still unsolved efficiently. This paper researches the 3-hypergraphic problem in terms of edge switching and exchanges in the sequence to implement Dewdney’s reduction. It proposes the idea of an irreducible decomposition and makes use of it to find some sufficient conditions for a 3-hypergraphic sequence. In addition, this paper explores a related problem: intersection preserving mappings. / May 2016
|
57 |
Parallel data-processing on GPGPU / Parallel data-processing on GPGPUVansa, Radim January 2012 (has links)
Modern graphic cards are no longer limited to 3D image rendering. Frameworks such as OpenCL enable developers to harness the power of many-core architectures for general-purpose data-processing. This thesis is focused on elementary primitives often used in database management systems, particularly on sorting and set intersection. We present several approaches to these problems and evalute results of benchmarked implementations. Our conclusion is that both tasks can be successfully solved using graphic cards with significant speedup compared to the traditional applications computing solely on multicore CPU.
|
58 |
On the derivation module and apolar algebra of an arrangement of hyperplanes /Wakefield, Max, January 2006 (has links)
Thesis (Ph. D.)--University of Oregon, 2006. / Typescript. Includes vita and abstract. Includes bibliographical references (leaves 83-84). Also available for download via the World Wide Web; free to University of Oregon users.
|
59 |
Analyzing Stratified Spaces Using Persistent Versions of Intersection and Local HomologyBendich, Paul 05 August 2008 (has links)
<p>This dissertation places intersection homology and local homology within the framework of persistence, which was originally developed for ordinary homology by Edelsbrunner, Letscher, and Zomorodian. The eventual goal, begun but not completed here, is to provide analytical tools for the study of embedded stratified spaces, as well as for high-dimensional and possibly noisy datasets for which the number of degrees of freedom may vary across the parameter space. Specifically, we create a theory of persistent intersection homology for a filtered stratified space and prove several structural theorems about the pair groups asso- ciated to such a filtration. We prove the correctness of a cubic algorithm which computes these pair groups in a simplicial setting. We also define a series of intersec- tion homology elevation functions for an embedded stratified space and characterize their local maxima in dimension one. In addition, we develop a theory of persistence for a multi-scale analogue of the local homology groups of a stratified space at a point. This takes the form of a series of local homology vineyards which allow one to assess the homological structure within a one-parameter family of neighborhoods of the point. Under the assumption of dense sampling, we prove the correctness of this assessment at a variety of radius scales.</p> / Dissertation
|
60 |
Accuracy Improvement of Closed-Form TDOA Location Methods Using IMM AlgorithmChen, Guan-Ru 31 August 2010 (has links)
For target location and tracking in wireless communication systems, mobile target positioning and tracking play an important role.
Since multi-sensor system can be used as an efficient solution to target positioning process, more accurate target location estimation and tracking results can be obtained.
However, both the deployment of designed multi-sensor and location algorithm may affect the overall performance of position location.
In this thesis, based on the time difference of arrival (TDOA), two closed-form least-square location methods, spherical-interpolation (SI) method
and spherical-intersection (SX) method are used to estimate the target location. The two location methods are different from the usual process of
iterative and nonlinear minimization.
The locations of the target and the designed multiple sensors may yield geometric effects on location performance.
The constraints and performance of the two location methods will first be introduced.
To achieve real-time target tracking, the Kalman filtering structures are used to combine the SI and SX methods.
Because these two positioning and tracking systems have different and complementary performance inside and outside the multi-sensor array, we consider using data fusion to improve location estimation results by using interacting multiple model (IMM) based estimator, in which internal filters running in parallel are designed as the SX-KF1 and the SI-KF2. However, due to the time-varying characteristics of measurement noises, we propose an adjusting scheme for measurement noise variance assignment in the Kalman filters to obtain improved location estimation results. Simulation results are obtained by running Matlab program.
In three-dimensional multi-sensor array scenarios, the
results of moving target location estimation shows that the IMM-based estimators effectively improve the position performance.
|
Page generated in 0.1156 seconds