Modular average case analysis: Language implementation and extension

Motivated by accurate average-case analysis, MOdular Quantitative Analysis (MOQA) is developed at the Centre for Efficiency Oriented Languages (CEOL). In essence, MOQA allows the programmer to determine the average running time of a broad class of programmes directly from the code in a (semi-)automated way. The MOQA approach has the property of randomness preservation which means that applying any operation to a random structure, results in an output isomorphic to one or more random structures, which is key to systematic timing. Based on original MOQA research, we discuss the design and implementation of a new domain specific scripting language based on randomness preserving operations and random structures. It is designed to facilitate compositional timing by systematically tracking the distributions of inputs and outputs. The notion of a labelled partial order (LPO) is the basic data type in the language. The programmer uses built-in MOQA operations together with restricted control flow statements to design MOQA programs. This MOQA language is formally specified both syntactically and semantically in this thesis. A practical language interpreter implementation is provided and discussed. By analysing new algorithms and data restructuring operations, we demonstrate the wide applicability of the MOQA approach. Also we extend MOQA theory to a number of other domains besides average-case analysis. We show the strong connection between MOQA and parallel computing, reversible computing and data entropy analysis.

Practical programming for static average-case analysis: the MOQA investigation

This work considers the static calculation of a program’s average-case time. The number of systems that currently tackle this research problem is quite small due to the difficulties inherent in average-case analysis. While each of these systems make a pertinent contribution, and are individually discussed in this work, only one of them forms the basis of this research. That particular system is known as MOQA. The MOQA system consists of the MOQA language and the MOQA static analysis tool. Its technique for statically determining average-case behaviour centres on maintaining strict control over both the data structure type and the labeling distribution. This research develops and evaluates the MOQA language implementation, and adds to the functions already available in this language. Furthermore, the theory that backs MOQA is generalised and the range of data structures for which the MOQA static analysis tool can determine average-case behaviour is increased. Also, some of the MOQA applications and extensions suggested in other works are logically examined here. For example, the accuracy of classifying the MOQA language as reversible is investigated, along with the feasibility of incorporating duplicate labels into the MOQA theory. Finally, the analyses that take place during the course of this research reveal some of the MOQA strengths and weaknesses. This thesis aims to be pragmatic when evaluating the current MOQA theory, the advancements set forth in the following work and the benefits of MOQA when compared to similar systems. Succinctly, this work’s significant expansion of the MOQA theory is accompanied by a realistic assessment of MOQA’s accomplishments and a serious deliberation of the opportunities available to MOQA in the future.

A review of road structure data in six European countries

The European Union has expanded significantly in recent years. Sustainable trade within the Union, leading to economic growth to the benefit of the ‘old’ and ‘new’ member states is thus extremely important. The road infrastructure is strategic and vital to such development since an uneven transport infrastructure, in terms of capacity and condition, has the potential to reinforce uneven development trends and hinder economic convergence of old and new member states. In the decades since their design and construction, loading conditions have significantly changed for many major highway infrastructure elements/networks owing primarily to increased freight volumes and vehicle sizes. This, coupled with the gradual deterioration of a significant number of highway structures due to their age, and the absence of a pan-European assessment framework, can be expected to affect the smooth functioning of the infrastructure in its as-built condition. Increased periods of reduced flow can be expected owing to planned and unplanned interventions for repair/rehabilitation. This paper reports the findings of a survey regarding the current status of the highway infrastructure elements in six countries within the European Union as reported by the owners/operators. The countries surveyed include a cross-section of ‘existing’ older countries and ‘new’ member states. The current situations for bridges, culverts, tunnels and retaining walls are reported, along with their potential replacement costs. The findings act as a departure point for further studies in support of a centralised and/or synchronised EU approach to infrastructure maintenance management. Information in the form presented in this paper is central to any future decision-making frameworks in terms of trade route choice and operations, monetary investment, optimised maintenance, management and rehabilitation of the built infrastructure and the economic integration of the newly joined member states.

Statistical methods for polyhedral shape classification with incomplete data - application to cryo-electron tomographic images

A certain type of bacterial inclusion, known as a bacterial microcompartment, was recently identified and imaged through cryo-electron tomography. A reconstructed 3D object from single-axis limited angle tilt-series cryo-electron tomography contains missing regions and this problem is known as the missing wedge problem. Due to missing regions on the reconstructed images, analyzing their 3D structures is a challenging problem. The existing methods overcome this problem by aligning and averaging several similar shaped objects. These schemes work well if the objects are symmetric and several objects with almost similar shapes and sizes are available. Since the bacterial inclusions studied here are not symmetric, are deformed, and show a wide range of shapes and sizes, the existing approaches are not appropriate. This research develops new statistical methods for analyzing geometric properties, such as volume, symmetry, aspect ratio, polyhedral structures etc., of these bacterial inclusions in presence of missing data. These methods work with deformed and non-symmetric varied shaped objects and do not necessitate multiple objects for handling the missing wedge problem. The developed methods and contributions include: (a) an improved method for manual image segmentation, (b) a new approach to 'complete' the segmented and reconstructed incomplete 3D images, (c) a polyhedral structural distance model to predict the polyhedral shapes of these microstructures, (d) a new shape descriptor for polyhedral shapes, named as polyhedron profile statistic, and (e) the Bayes classifier, linear discriminant analysis and support vector machine based classifiers for supervised incomplete polyhedral shape classification. Finally, the predicted 3D shapes for these bacterial microstructures belong to the Johnson solids family, and these shapes along with their other geometric properties are important for better understanding of their chemical and biological characteristics.

Self-assembly of gold nanocrystals into discrete coupled plasmonic structures

Development of methodologies for the controlled chemical assembly of nanoparticles into plasmonic molecules of predictable spatial geometry is vital in order to harness novel properties arising from the combination of the individual components constituting the resulting superstructures. This paper presents a route for fabrication of gold plasmonic structures of controlled stoichiometry obtained by the use of a di-rhenium thio-isocyanide complex as linker molecule for gold nanocrystals. Correlated scanning electron microscopy (SEM)—dark-field spectroscopy was used to characterize obtained discrete monomer, dimer and trimer plasmonic molecules. Polarization-dependent scattering spectra of dimer structures showed highly polarized scattering response, due to their highly asymmetric D∞h geometry. In contrast, some trimer structures displayed symmetric geometry (D3h), which showed small polarization dependent response. Theoretical calculations were used to further understand and attribute the origin of plasmonic bands arising during linker-induced formation of plasmonic molecules. Theoretical data matched well with experimentally calculated data. These results confirm that obtained gold superstructures possess properties which are a combination of the properties arising from single components and can, therefore, be classified as plasmonic molecules