Chiral gold complexes have been applied in homogeneous catalytic reactions since 1986, in some cases with high enantioselectivity. Acyclic diaminocarbene (ADC) ligands are acyclic analogues of N-heterocyclic carbenes (NHCs) that have larger N-CCarbene-N angles and stronger donating ability. ADCs have been developed as alternatives to phosphine and NHC ligands in homogeneous gold catalysis. In 2012, a new series of chiral gold(I) ADCs were first developed by Slaughter's group and were shown to give remarkable enantioselectivities in some reactions. Because of the hindered rotation of the N-CCarbene bonds of ADC, chiral ADC substituents can easily get close to the metal center in some conformations, although two rotameric structures are formed if the chiral amine is nonsymmetric. The selective of specific ADC conformations was the initial focus of this study. Formational selectivity of one diastereomer of an ADC ligand during synthesis was examines by measuring the relative rates of diastereomer formation in a 1H NMR kinetic study. The potential for converting multiple conformational isomers of ADCs into a single conformation, or at least a simpler mixture, was examined. This study used the analogy that anti- isomer has electronic and structural similarity with urea/thiourea, raising the possibility that 1,8-naphthyridine can be used to favor certain conformations through a self-assembled hydrogen-bonding complex. Gold(I) is a soft carbophilic Lewis acid able to active C-C π bonds to nucleophilic attack, and ADC-gold complexes are potentially useful in this regard. Therefore, biaryl gold(I) ADC complexes were examine with silver salt additives in catalytic 1,6-enyne cyclization reaction. A detailed study found that the counteranion affects the regioselectivities of these reactions more than substituents on the ancillary ADC ligands.

This thesis is submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Ph.D) in the FASTAR group of the Department of Computer Science, University of Pretoria, South Africa. I present a number of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs), most of which I originally derived/designed or co-discovered. Being acyclic, such automata represent finite languages and have proven useful in applications such as spellchecking, virus-searching and text indexing. In many of those applications, the automata grow to billions of states, making them difficult to store without using various compression techniques — the most important of which is minimization. Results from the late 1950’s show that minimization yields a unique automaton (for a given language), and later results show that minimization of acyclic automata is possible in time linear in the number of states. These two results make for a rich area of algorithmics research; automata and algorithmics research are relatively old fields of computing science and the discovery/invention of new algorithms in the field is an exciting result. I present both incremental and nonincremental algorithms. With nonincremental techniques, the unminimized acyclic deterministic finite automaton (ADFA) is first constructed and then minimized. As mentioned above, the unminimized ADFA can be very large indeed — often even too large to fit within the virtual memory space of the computer. As a result, incremental techniques for minimization (i.e. the ADFA is minimized during its construction) become interesting. Incremental algorithms frequently have some overhead: if the unminimized ADFA fits easily within physical memory, it may still be faster to use nonincremental techniques. The presentation used in this thesis has a few unusual characteristics: <ul><li> Few other presentations follow a correctness-by-construction style for presenting and deriving algorithms. The presentations given here include correctness arguments or sketches thereof. </li><li> The presentation is taxonomic — emphasizing the similarities and differences between the algorithms at a fundamental level. </li><li> While it is possible to present these algorithms in a formal-language-theoretic setting, this thesis remains somewhat closer to the actual implementation issues. </li><li> In several chapters, new algorithms and interesting new variants of existing algorithms are presented. </li><li> It gives new presentations of many existing algorithms — all in a common format with common examples. </li><li> There are extensive links to the existing literature. </li></ul> / Thesis (PhD)--University of Pretoria, 2010. / Computer Science / unrestricted

Continuous advances in VLSI technology have led to more complex digital designs and shrinking transistor sizes. Due to these developments, design verification and manufacturing test have gained more importance and 70 % of the design expenditure in on validation processes. Electronic Design Automation (EDA) tools play a huge role in the validation process with various verification and test tools. Their efficiency have a high impact in saving time and money in this competitive market. Direct Acyclic Graphs (DAGs) are the backbone for most of the EDA tools. DAG is the most efficient data structure to store circuit information and also have efficient backt traversing structure which help in developing reasoning/ debugging tools. In this thesis, we focus on two such EDA tools using graphs as their underlying structure for circuit information storage • Scan pattern Debugger for Partial Scan Designs • Circuit SAT Bounded Model Checkers We developed a complete Interactive Scan Pattern Debugger Suite currently being used in the industry for next generation microprocessor design. The back end is an implication graph based sequential logic simulator which creates a Debug Implication Graph during the logic simulation of the failing patterns. An efficient node traversal mechanism across time frames, in the DIG, is used to perform the root-cause analysis for the failing scan-cells. In addition, the debugger provides visibility into the circuit internals to understand and fix the root-cause. We integrated the proposed technique into the scan ATPG flow for industrial microprocessor designs. We were able to resolve the First Silicon logical pattern failures within hours, which would have otherwise taken a few days of manual effort for root-causing the failure, understanding the root-cause and fixing it. For our circuit SAT implementation, we replace the internal implication graph used by the SAT solver with our debug implication graph (DIG). There is a high amount of circuit unrolling in circuit SAT/ BMC (Bounded Model Checking) problems which creates copies of the same combinational blocks in multiple time frames. This allows us to use the repetitive circuit structure and club it with the CNF database in the SAT solver. We propose a new data structure to store data in a circuit SAT solver which results up to 90% reduction in number of nodes. / Master of Science

This thesis deals with the preparation of acyclic nucleosides and nucleoside phosphonates of compounds T-705 (6-fluoro-3-hydroxypyrazine-2-carboxamide) and T-1105 (3-hydroxypyrazine-2-carboxamide). Acyclic nucleoside phosphonates are substances that can terminate viral RNA or DNA replication, and some of them are used in the treatment of viral diseases. T-705 and T-1105 have shown activity against the influenza virus, and T-705 has already been approved for its treatment in Japan. Since both compounds mimic natural nucleobases in the body, their acyclic nucleosides and nucleoside phosphonates also have the potential to be biologically active. Methods for the synthesis of 3-fluoro-2-(phosphonomethoxy)propyl and 3-hydroxy-2-(phosphonomethoxy)propyl derivatives of T-705 and T-1105, their prodrugs containing lipophilic groups for the improvement of the pharmacokinetic properties and also their phosphonate diphosphates, suitable for the biological activity measurements, have been proposed. Some of these derivatives were subsequently prepared. Key words: acyclic nucleosides, acyclic nucleoside phosphonates, T-705, T-1105, favipiravir, antiviral activity, influenza

Many previous studies have demonstrated that gold compounds possess successful results in catalysis and in medicinal chemistry. The central aim of this dissertation is the design and synthesis of novel gold (I) acyclic diamino carbene complexes as a chemotherapeutic agent for triple-negative breast cancer (TNBC) and for catalysis. In this study, a series of chiral neutral and cationic gold (I) acyclic diamino carbene (ADC) complexes and neutral gold (I) bis- ADC complexes have been synthesized. As the chiral neutral gold (I) ADCs, four diastereomers of S binaphthyl L proline tertiary butyl ester gold (I) chloride, S binaphthyl D proline tertiary butyl ester gold (I) chloride, R binaphthyl L proline tertiary butyl ester gold (I) chloride, and R binaphthyl D proline tertiary butyl ester gold (I) chloride have been synthesized and characterized. Different chiral gold (I) ADC complexes with bulky chiral binaphthyl group and with different amine groups of morpholine, chiral proline methyl ester, and benzyl ester have been synthesized and characterized. After that four diastereomers of the nitrile adduct of cationic binaphthyl proline tertiary butyl ester nitrile and four diastereomers of the isonitrile versions of it have been synthesized and characterized. A series of gold (I) cationic bis ADC complexes have been synthesized and characterized. All these novel gold ADC complexes were tested for biological activity against TNBC cell line MDA-MB-231 and cationic S binaphthyl D proline ester isonitrile adduct, S binaphthyl D proline ester isonitrile adduct and R binaphthyl D proline ester isonitrile adduct gave promising inhibition rates. According to Lipinski's rule, lipophilicity determines the effectiveness of the drug absorption to the body through the lipid membrane. To determine the drug-likeness of the gold ADC complexes, log P values were calculated for some of the synthesized complexes using a modified shake flask method. Gold (I) ADC complexes have been renowned for their ability in catalysis, but enantioselective catalysis is not that well studied. A3 coupling reaction is a well-known reaction for the synthesis of propargyl amines. Here, A3 coupling reaction with a chiral amine has been performed using the previously synthesized four diastereomers of binaphthyl proline tertial butyl ester gold (I) ADCs (SL, RD, RL, SD) as the catalyst expecting four different diastereomers of the product. The reaction exhibited reasonable yields but with a low enantiomeric excess (ee%). However, it gave proof of the principle that asymmetric induction is possible with the synthesized novel chiral gold (I) ADC complexes.

Les 1,3-diols acycliques sont des motifs ubiquitaires, essentiels dans la structure de nombreux produits naturels. Le développement d’approches permettant leur obtention de manière énantiosélective se révèle donc d’un grand intérêt synthétique. Dans ce contexte, notre équipe a envisagé une stratégie reposant sur des transferts d’acyle énantiosélectifs organocatalysés multiples. Cette approche a abouti à la mise en oeuvre d’une méthodologie de désymétrisation énantiosélective organocatalysée de 1,3-diols méso acycliques. Les composés ainsi obtenus constituent des briques moléculaires aisément valorisables en synthèse totale. Une approche similaire a permis de décrire, dans un second temps, une méthode inédite de double dédoublement cinétique de 1,3-diols anti. Générale et pratique, ce procédé fournit des diols énantiopurs de structures variées. La particularité de ces méthodologies réside dans l’exploitation du principe de Horeau se traduisant par une amplification de l’énantiosélectivité déployée par le catalyseur chiral. Les isothiourées employés dans ces réactions constituent une famille de bases de Lewis azotées dont la capacité à promouvoir les réactions d’acylation énantiosélectives n’a été découverte que récemment. Bien que leur utilisation en catalyse énantiosélective se soit rapidement démocratisée, les éléments structuraux responsables de leur sélectivité n’ont pas été totalement identifiés. Avec le nouvel objectif d’établir une relation entre structure, réactivité et sélectivité de ces molécules, des isothiourées originales ont été synthétisées et leur potentiel catalytique étudié en détail. / Acyclic 1,3-diols are ubiquitous scaffolds, essential in the structure of numerous natural products. The developpment of innovative pathways allowing their enantioselective obtention is of first interst in organic synthesis. In this context, our team envisaged a strategy of multiple organocatalyzed enantioselective acyl transfers. This approach led to the implement of a methodology based on the organocatalyzed desymmetrization of meso 1,3-diols. The desymmetrized compounds were obtained with high level of enantioselectivity and were used as useful building blocks easily valorizable in total synthesis. In a second time, we developed an organocatalyzed method of double kinetic resolution (DoCKR) of anti 1,3-diols. Very general, practicable and useful, this process allows the preparation of enantiopur diols with a large structural diversity. The particularity of these methods reside in the exploitation of the Horeau principle leading to the amplification of the enantioselectivity. These phenomons of kinetic amplification, often anecdotic, were used in this study as a powerful tool.The employed isothioureas belong to the nitrogenated Lewis bases family which were discovered only very recently to promote enantioselective acyl transfer. Although their uses in enantioselective catalysis were rapidly democratized, the structural feature responsible of their selectivity are not all clearly identified. To establish a relationship between structure, reactivity and selectivity of theses molecules, new isothioureas were synthesized and evaluated in enantioselective catalysis.

A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum number of colors required to acyclically edge color G. The primary motivation for this thesis is the following conjecture by Alon, Sudakov and Zaks [7] (and independently by Fiamcik [22]): Acyclic Edge Coloring Conjecture: For any graph G, a’ (G) ≤ Δ(G)+2. The following are the main results of the thesis: 1 From a result of Burnstein [16], it follows that any subcubic graph can be acyclically edge colored using at most 5 colors. Skulrattankulchai [38] gave a polynomial time algorithm to color a subcubic graph using Δ + 2 = 5 colors. We proved that any non-regular subcubic graph can be acyclically colored using only 4 colors. This result is tight. This also implies that the fifth color, when needed is required only for one edge. 2 Let G be a connected graph on n vertices, m ≤ 2n - 1 edges and maximum degree Δ ≤ 4, then a’ (G) ≤ 6. This implies that graph of maximum degree 4 are acyclically edge colorable using at most 7 colors. 3 The earliest result on acyclic edge coloring of 2-degenerate graphs was by Caro and Roditty [17], where they proved that a’ (G) ≤ Δ + k - 1, where k is the maximum edge connectivity, defined as k = maxu,vε V(G)λ(u,v), where λ(u,v)is the edge-connectivity of the pair u,v. Note that here k can be as high as Δ. Muthu,Narayanan and Subramanian [34] proved that a’ (G) ≤ Δ + 1for outerplanar graphs which are a subclass of 2-degenerate graphs and posed the problem of proving the conjecture for 2-degenerate graphs as an open problem. In fact they have also derived an upper bound of Δ+1 for series-parallel graphs [35], which is a slightly bigger subclass of 2-degenerate graphs. We proved that 2-degenerate graphs are Δ+1colorable. 1 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of 2Δ+29 for planar graphs. Independently Hou, Wu, GuiZhen Liu and Bin Liu [29] gave an upper bound of max(2Δ - 2,Δ+ 22). We improve this upper bound to Δ+12, which is the best known bound at present. 2 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of Δ+6for triangle free planar graphs. We improve the bound to Δ+3, which is the best known bound at present. 3 We have also worked on lower bounds. Alon et.al. [7], along with the acyclic edge coloring conjecture, also made an auxiliary conjecture stating that Complete graphs of 2n vertices are the only class of regular graphs which require Δ+2colors. We disproved this conjecture by showing infinite classes of regular graphs other than Complete Graphs which require Δ+2colors. Apart from the above mentioned results, this thesis also contributes to the acyclic edge coloring literature by introducing new techniques like Recoloring, Color Exchange (exchanging colors of adjacent edges), circular shifting of colors on adjacent edges (derangement of colors). These techniques turn out to be very useful in proving upper bounds on the acyclic edge chromatic number.

No description available.

A. Ádám conjectured that for any non-acyclic digraph D, there exists an arc whose reversal reduces the total number of cycles in D. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address a conjecture of Reid [Rei84] that Ádám's conjecture is true for tournaments that are 3-arc-connected but not 4-arc-connected.

With the ever expanding utility of transition metal catalysis, there has been a thrust both to develop catalysts with unique selectivites or activites, and to understand the factors which govern these characteristics at both a fundamental and practical level. Olefin metathesis has become an essential reaction for the synthesis of small molecules in addition to polymeric materials. We have pursued two distinct ligand classes based on diaminocarbenes with novel architectures to address specific limitations within this useful class of reactions: 1) limited access to polymeric materials with controlled microstructures and 2) poor stereoselectivity in Ru-catalyzed cross-metathesis (CM) reactions. Numerous phosphines and N-heterocyclic carbenes (NHCs) have been used as ligands for Ru metathesis catalysts, and the resulting activity is very sensitive to their steric and electronic nature. We envisioned that we could take advantage of this dependence by developing a catalyst with tunable ligand donicity. Redox-switchable ligands can lead to catalysts whose selectivity and/or activity are dependent upon the ligand oxidation state. Towards this purpose, we have developed a ligand which incorporates a 1,1’-disubstituted ferrocene moiety into the backbone of a diaminocarbene (FcDAC). Upon ligation of FcDAC to various transition metals, we were able to use cyclic voltammetry and a spectroelectrochemical FT-IR experiment to show electronic communication between FcDAC and the coordinated metal. We then pursued Ru metathesis catalysts incorporating these ligands. The ring-opening metathesis polymerization of 1,5-cyclooctadiene was studied using [(FcDAC)(PPh₃)Cl₂Ru=(3-phenylindenylid-2-ene)] as the catalyst. Chemical redox reactions were used to establish the ability of FcDAC to impart redox-tunable properties to Ru metathesis catalysts. A new ligand class pioneered in our group, N-aryl,N-alkyl acyclic diaminocarbenes (ADCs), was also studied in various Ru metathesis catalysts. To our delight, these catalysts showed lower E : Z ratios than analogous NHC ligands in two representative CM reactions. We also investigated the conformational diversity of these differentially substituted ADCs given their ability to rotate about their C–N bonds, in particular, to determine how this might influence their donicity. Complexes of the type [(ADC)Ir(COD)Cl] and [(ADC)Ir(CO)₂Cl] were studied, given the wealth of structural and spectral data available for analogous compounds incorporating related ligand classes. Different conformations resulted depending on the N-substituents and the nature of the metal complex. Interestingly, the electron donating ability of ADC ligands was found to depend on their conformation, as evidenced by FT-IR and cyclic voltammetry. This established a new avenue for tuning the donor properties of differentially substituted ADC ligands. The unique properties of these novel ligand classes were demonstrated in Ru metathesis catalysts. However, on a broader level, these ligands are expected to have utility in diverse catalytic applications. / text