The orientation completion problem for a hereditary class C of oriented graphs asks whether a given partially oriented graph can be completed to a graph belonging to C. This problem was introduced recently and is a generalization of several existing problems, including the recognition problem for certain classes of graphs and the representation extension problem for proper interval graphs. A local tournament is an oriented graph in which the in-neighbourhood as well as the out-neighbourhood of each vertex induces a tournament. Local tournaments are a well-studied class of oriented graphs that generalize tournaments and their underlying graphs are intimately related to proper circular-arc graphs. Proper interval graphs are precisely those which can be oriented as acyclic local tournaments. The orientation completion problems for the class of local tournaments and the class of acyclic local tournaments have been shown to be polynomial-time solvable. In this thesis, we characterize the partially oriented graphs that can be completed to local tournaments by finding a complete list of obstructions. These are in a sense the minimal partially oriented graphs that cannot be completed to local tournaments. We also determine the minimal partially oriented graphs that cannot be completed to acyclic local tournaments. / Graduate

No description available.

Relational data is characterised by the rich structure it encodes in the dependencies between the individual entities of a given domain. Statistical Relational Learning (SRL) combines first-order logic and probability to learn and reason over relational domains by creating parametric probability distributions over relational structures. SRL models can succinctly represent the complex dependencies in relational data and admit learning and inference under uncertainty. However, these models are significantly limited when it comes to the tractability of learning and inference. This limitation emerges from the intractability of Weighted First Order Model Counting (WFOMC), as both learning and inference in SRL models can be reduced to instances of WFOMC. Hence, fragments of first-order logic that admit tractable WFOMC, widely known as domain-liftable, can significantly advance the practicality and efficiency of SRL models. Recent works have uncovered another limitation of SRL models, i.e., they lead to unintuitive behaviours when used across varying domain sizes, violating fundamental consistency conditions expected of sound probabilistic models. Such inconsistencies also mean that conventional machine learning techniques, like training with batched data, cannot be soundly used for SRL models. In this thesis, we contribute to both the tractability and consistency of probabilistic inference in SRL models. We first expand the class of domain-liftable fragments with counting quantifiers and cardinality constraints. Unlike the algorithmic approaches proposed in the literature, we present a uniform combinatorial approach, admitting analytical combinatorial formulas for WFOMC. Our approach motivates a new family of weight functions allowing us to express a larger class of probability distributions without losing domain-liftability. We further expand the class of domain-liftable fragments with constraints inexpressible in first-order logic, namely acyclicity and connectivity constraints. Finally, we present a complete characterization for a statistically consistent (a.k.a projective) models in the two-variable fragment of a widely used class of SRL models, namely Markov Logic Networks.

No description available.

No description available.

No description available.

A set of five new C3-symmetric phosphites were synthesized and tested in palladium-catalyzed asymmetric Suzuki coupling. The observed reactivity and selectivity were dependent upon several factors. One of the phosphites was able to achieve some of the highest levels of enantioselectivity in asymmetric Suzuki couplings with specific substrates. Different hypotheses have been made for understanding the ligand effects and reaction selectivities, and those hypotheses were tested via various methods including DOSY NMR experiments, X-ray crystallography, and correlation of catalyst selectivity with Tolman cone angles. Although only modest enantioselectivities were observed in most reactions, the ability to synthesis these phosphites in only three steps on gram scales and to readily tune their properties by simple modification of the binaphthyl 2´-substituents makes them promising candidates for determining structure-selectivity relationships in asymmetric transition metal catalysis, in which phosphites have been previously shown to be successful. A series of novel chiral oxazoline-based carbodicarbene ligands was targeted for synthesis. Unfortunately, the chosen synthetic route could not be completed due to unwanted reactivity of the oxazoline ring. However, a new and efficient route for Pd-catalyzed direct amination of aryl halides with oxazoline amine was developed and optimized during these studies. Chiral binaphthyl based Pd(II) ADC complexes with different substituent groups have been synthesized and tested in asymmetric Suzuki coupling reactions. Although only low enantioselectivities were observed in Suzuki coupling, this represents a new class of chiral metal-ADC catalysts that could be tested in further catalytic.

Carbene ligands over these years have become a heavily utilizes and effective ligand for catalysis. The diamino carbene class of ligands are slightly less understood. The effects of bis(carbene) ligand structures of palladium (II) catalysts were investigated using the ETS-NOCV method. The results showed that the amount of π-backbonding played a major role in the rate of the reaction for these NHC complexes. The amount of pi acceptance from the ligand increased in correlation to the length of the methylene linkage in the ligand back bone resulting in increased catalytic activity. The ETS-NOCV method was used to determine the deformation densities that had a contribution to this interaction based on visual interpretation. The percent contribution of pi interactions provided a linear correlation to the natural log of the initial reaction rate, indicating that π-backbonding plays a crucial role in the overall catalytic activity of the palladium complexes. Gold (I) bis acyclic diamino carbenes (ADCs) were investigated for the possibility to be strong hydrogen bond catalysts. The ligand motif of the gold (I) bisADCs were found to be analogous thiourea compounds. Based on NBO analysis there were some improvements to hydrogen bond donicity in comparison to thioureas with the same functional group. The complexes were analyzed for hydrogen bond interactions and polarizations interactions between simple nitroolefin substrate and the catalyst using ETS-NOCV. Results showed that the compounds can form a stable hydrogen bonding system and activate the substrate. This capability is tunable by changing the electron withdrawing properties of the ligase motif, providing the idea that gold (I) bisADCs have potential to be good hydrogen bond catalysts. New thiourea-like gold (I) catalysts utilizing the acyclic diamino carbene motif that were hypothesized were synthesized using a one pot synthesis approach utilizing a metal templated synthesis method. The synthesis, characterization, and application prove these complexes with their cationic centers and bisADCs ligand motif can be utilized for Friedel-Crafts alkylation of indoles, resulting in the production of three new compounds to literature. This research also provided a new application for this specific ligand class and further proved the robustness of ADC ligands.

[pt] Este trabalho é uma elaboração, com exemplos, e evolução do Algoritmo de Compressão Horizontal (HC) apresentado e seu Conjunto de Regras de Compressão. Este trabalho apresenta uma prova, feita no Provador Interativo de Teoremas Lean, de que o algoritmo HC pode obter uma Derivação Comprimida, representada por um Grafo Acíclico Dirigido, a partir de qualquer Derivação Tipo-Árvore em Dedução Natural para a Lógica Minimal Puramente Implicacional. Finalmente, a partir da Cobertura e Corretude do algoritmo HC, pode-se argumentar que NP = PSPACE. / [en] This work is an elaboration, with examples, and evolution of the presented Horizontal Compression Algorithm (HC) and its set of Compression Rules. This work argues a proof, done in the Lean Interactive Theorem Prover, that the HC algorithm can obtain a Compressed Derivation, represented by a Directed Acyclic Graph, from any Tree-Like Natural Deduction Derivation in Minimal Purely Implicational Logic. Finally, from the Coverage and Soundness of the HC algorithm, one can argue that NP = PSPACE.

Invasive alien plants have widespread ecological and socioeconomic impacts throughout many parts of the world, including Swaziland where the government declared them a national disaster. Control of these species requires knowledge on the invasion ecology of each species including how they interact with the invaded environment. Species distribution models are vital for providing solutions to such problems including the prediction of their niche and distribution. Various modelling approaches are used for species distribution modelling albeit with limitations resulting from statistical assumptions, implementation and interpretation of outputs. This study explores the usefulness of Bayesian networks (BNs) due their ability to model stochastic, nonlinear inter-causal relationships and uncertainty. Data-driven BNs were used to explore patterns and processes influencing the spatial distribution of 16 priority invasive alien plants in Swaziland. Various BN structure learning algorithms were applied within the Weka software to build models from a set of 170 variables incorporating climatic, anthropogenic, topo-edaphic and landscape factors. While all the BN models produced accurate predictions of alien plant invasion, the globally scored networks, particularly the hill climbing algorithms, performed relatively well. However, when considering the probabilistic outputs, the constraint-based Inferred Causation algorithm which attempts to generate a causal BN structure, performed relatively better. The learned BNs reveal that the main pathways of alien plants into new areas are ruderal areas such as road verges and riverbanks whilst humans and human activity are key driving factors and the main dispersal mechanism. However, the distribution of most of the species is constrained by climate particularly tolerance to very low temperatures and precipitation seasonality. Biotic interactions and/or associations among the species are also prevalent. The findings suggest that most of the species will proliferate by extending their range resulting in the whole country being at risk of further invasion. The ability of BNs to express uncertain, rather complex conditional and probabilistic dependencies and to combine multisource data makes them an attractive technique for species distribution modeling, especially as joint invasive species distribution models (JiSDM). Suggestions for further research are provided including the need for rigorous invasive species monitoring, data stewardship and testing more BN learning algorithms. / Environmental Sciences / D. Phil. (Environmental Science)