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.

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)

論文提要內容： 圖論上，定義兩點相似（similar ）：若a ，b 是圖G 上的兩點，且存在一個定義於 V （G ）的某排列φ，滿足：（１）φAut（G）及（２）φ（a）＝b，則稱G 之a，b 兩點相似。由定義吾人固然知必有一φ Aut（G），滿足φ（a）＝b，如果G 之a，b 兩點相似的話。然而，有人不禁會問：若G 上任二點a，b相似 ，則是否存在一φ Aut（G），同時滿足φ（a）＝b且φ（b）＝a呢?（ 本文稱G 為 對稱相似（symmet-rically similar），若答案為真時。） 作者在研究GRAPH RECONSTRUCTION CONJECTURE 時，亦產生相同的疑問。本文乃作者 試就此一問題，將樹形圖（Tree）加以研究，發現：凡是具有有限點的樹形圖（fin- ite tree）皆具備此特性。 本文共分二章四節。首先，吾人知：任意樹形圖乃一不具環路的聯結圖（acyclic c- onnected graph），且任二不同點a ，b 僅可決定出唯一的（a－b）路徑（ path ） 。 本文先針對此路徑觀察出二項特性：（１）當（a－b）為偶路徑，m 為其中點，且φ （a）＝b，φ Aut（G）時，φ作用在m，n之後對調（即φ（m）＝n且φ（n ）＝ m 。其證明包含在定理２．１．７及定理２．１．９之中。 其次，以定理２．１．７及定理２．１．９為基礎，本文將證明出：確實存在－φ Aut（G），同時滿足φ（a）＝b且φ（b）＝a，此處G 為一樹形圖。 由於找不到反例，本文將給一個Conjecture作為總結，即：任一有限simple圖皆具對 稱相似性。