Algebraic theory of minimal nondeterministic finite automata with applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA’s behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

The impact of bandwidth in structured interviewing and criterion stability in predicting and assessing manager performance across transition and maintenance stages

The current study examined the role of three important components in the use of structured employment interviewing in performance prediction: construct bandwidth, observed communication skill, and the stability/dynamicity of performance criteria over time. A matched sample of 242 hospitality managers was derived from a field data set provided by a large hospitality management organization. Interview data and two years of performance appraisal data were provided. Bandwidth analysis demonstrated only minimal differences in prediction between matched predictor-criterion pairs compared with predictor to overall aggregate ratings (unmatched). The communication skill analysis revealed that this interviewer rated observation significantly predicted a number of the individual performance dimensions as well as overall performance over time. Of the five interview items, the strongest overall predictor of performance was interviewer rated communication skill. The stability/dynamicity analyses demonstrated the performance criteria to be generally stable over the two year period examined, which provides support for the long held notion that performance criteria is stabile over time. However, there were two exceptions. The interview dimension customer service orientation had shifting relationships over time with four of the criteria over the two year period. The performance criteria employee development also demonstrated some instability in its relationships with predictors. Thus, some evidence of dynamicity in performance criteria was revealed. Interestingly, both of the most noteworthy findings in the study involved items that were rated differently than the others in the study. The rated interview item communication skill and the rated performance criteria client satisfaction were ratings that involved a more direct level of observation. Additional analyses also revealed evidence of a general factor of performance. These two themes are more fully covered in the discussion.

The discrimination and association of float glass and the quantitative analysis of liquids from aerosols and microdrops using laser induced breakdown spectroscopy

Glass is a common form of trace evidence found at many scenes of crimes in the form of small fragments. These glass fragments can transfer to surrounding objects and/or persons and may provide forensic investigators valuable information to link a suspect to the scene of a crime. Since the elemental composition of different glass sources can be very similar, a highly discriminating technique is required to distinguish between fragments that have originated from different sources. ^ The research presented here demonstrates that Laser Induced Breakdown Spectroscopy (LIBS) is a viable analytical technique for the association and discrimination of glass fragments. The first part of this research describes the optimization of the LIBS experiments including the use of different laser wavelengths to investigate laser-material interaction. The use of a 266 nm excitation laser provided the best analytical figures of merit with minimal damage to the sample. The resulting analytical figures of merit are presented. The second part of this research evaluated the sensitivity of LIBS to associate or discriminate float glass samples originating from the same manufacturing plants and produced at approximately the same time period. Two different sample sets were analyzed ranging in manufacturing dates from days to years apart. Eighteen (18) atomic emission lines corresponding to the elements Sr, K, Fe, Ca, Al, Ba, Na, Mg and Ti, were chosen because of their detection above the method detection limits and for presenting differences between the samples. Ten elemental ratios producing the most discrimination were selected for each set. When all the ratios are combined in a comparison, 99% of the possible pairs were discriminated using the optimized LIBS method generating typical analytical precisions of ∼5% RSD. ^ The final study consisted of the development of a new approach for the use of LIBS as a quantitative analysis of ultra-low volume solution analysis using aerosols and microdrops. Laser induced breakdown spectroscopy demonstrated to be an effective technique for the analysis of as low as 90 pL for microdrop LIBS with 1 pg absolute LOD and 20 µL for aerosol LIBS with an absolute LOD of ∼100 fg.^

A Minimal History of the Cuban Revolution (Historia mínima de Ia Revolución Cubana), Book Presentation by Author Rafael Rojas

This flyer promotes the event "A Minimal History of the Cuban Revolution (Historia mínima de Ia Revolución Cubana), Book Presentation by Author Rafael Rojas", part at the SIPA at Books & Books series. This event held at Books & Books in Coral Gables.

Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

A minimal model of partial synchrony

Acknowledgement We wish to acknowledge A. Pikovsky and M. Zaks for useful discussions. This work has been financially supported by the EU project COSMOS (642563).

A minimal model of partial synchrony

We wish to acknowledge A Pikovsky and M Zaks for useful discussions. This work has been financially supported by the EU project COSMOS (642563).

L'évaluation de l'action préventive en contexte d'imprévisibilité : les enjeux d'un projet de prévention des MTS/VIH/SIDA par les pairs, Amazonas, Brésil

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Development and Characterization of Monovalent and Bivalent RNA Aptamers Targeting the Common Pathway of Coagulation

Anticoagulant agents are commonly used drugs to reduce blood coagulation in acute and chronic clinical settings. Many of these drugs target the common pathway of coagulation because it is critical for thrombin generation and disruption of this portion of the pathway has profound effects on the hemostatic process. Currently available drugs for these indications struggle with balancing desired activity with immunogenicity and poor reversibility or irreversibility in the event of hemorrhage. While improvements are being made with the current drugs, new drugs with better therapeutic indices are needed for surgical intervention and chronic indications to prevent thrombosis from occurring.

A class of therapeutics known as aptamers may be able to meet the need for safer anticoagulant agents. Aptamer are short single-stranded RNA oligonucleotides that adopt specific secondary and tertiary structures based upon their sequence. They can be generated to both enzymes and cofactors because they derive their inhibitory activity by blocking protein-protein interactions, rather than active site inhibition. They inhibit their target proteins with a high level of specificity and bind with high affinity to their target. Additionally, they can be reversed using two different antidote approaches, specific oligonucleotide antidotes, or with cationic, “universal” antidotes. The reversal of their activity is both rapid and durable.

The ability of aptamers to be generated to cofactors has been conclusively proven by generating an aptamer targeting the common pathway coagulation cofactor, Factor V (FV). We developed two aptamers with anticoagulant ability that bind to both FV and FVa, the active cofactor. Both aptamers were truncated to smaller functional sizes and had specific point mutant aptamers developed for use as controls. The anticoagulant activity of both aptamer-mutant pairs was characterized using plasma-based clotting assays and whole blood assays. The mechanism of action resulting in anticoagulant activity was assessed for one aptamer. The aptamer was found to block FVa docking to membrane surfaces, a mechanism not previously observed in any of our other anticoagulant aptamers.

To explore development of aptamers as anticoagulant agents targeting the common pathway for surgical interventions, we fused two anticoagulant aptamers targeting Factor X and prothrombin into a single molecule. The bivalent aptamer was truncated to a minimal size while maintaining robust anticoagulant activity. Characterization of the bivalent aptamer in plasma-based clotting assays indicated we had generated a very robust anticoagulant therapeutic. Furthermore, we were able to simultaneously reverse the activity of both aptamers with a single oligonucleotide antidote. This rapid and complete reversal of anticoagulant activity is not available in the antithrombotic agents currently used in surgery.

A Search for a New Particle Decaying to Pairs of Weak Gauge Bosons with the ATLAS Detector

A search for new heavy resonances decaying to boson pairs (WZ, WW or ZZ) using 20.3 inverse femtobarns of proton-proton collision data at a center of mass energy of 8 TeV is presented. The data were recorded by the ATLAS detector at the Large Hadron Collider (LHC) in 2012. The analysis combines several search channels with the leptonic, semi-leptonic and fully hadronic final states. The diboson invariant mass spectrum is studied for local excesses above the Standard Model background prediction, and no significant excess is observed for the combined analysis. 95$\%$ confidence limits are set on the cross section times branching ratios for three signal models: an extended gauge model with a heavy W boson, a bulk Randall-Sundrum model with a spin-2 graviton, and a simplified model with a heavy vector triplet. Among the individual search channels, the fully-hadronic channel is predominantly presented where boson tagging technique and jet substructure cuts are used. Local excesses are found in the dijet mass distribution around 2 TeV, leading to a global significance of 2.5 standard deviations. This deviation from the Standard Model prediction results in many theory explanations, and the possibilities could be further explored using the LHC Run 2 data.

Levi-flat Minimal Hypersurfaces in Two-dimensional Complex Space Forms

The purpose of this article is to classify the real hypersurfaces in complex space forms of dimension 2 that are both Levi-flat and minimal. The main results are as follows: When the curvature of the complex space form is nonzero, there is a 1-parameter family of such hypersurfaces. Specifically, for each one-parameter subgroup of the isometry group of the complex space form, there is an essentially unique example that is invariant under this one-parameter subgroup. On the other hand, when the curvature of the space form is zero, i.e., when the space form is complex 2-space with its standard flat metric, there is an additional `exceptional' example that has no continuous symmetries but is invariant under a lattice of translations. Up to isometry and homothety, this is the unique example with no continuous symmetries.

Occurrence and Function of Hoogsteen Base Pairs in Nucleic Acids

Nucleic acids (DNA and RNA) play essential roles in the central dogma of biology for the storage and transfer of genetic information. The unique chemical and conformational structures of nucleic acids – the double helix composed of complementary Watson-Crick base pairs, provide the structural basis to carry out their biological functions. DNA double helix can dynamically accommodate Watson-Crick and Hoogsteen base-pairing, in which the purine base is flipped by ~180° degrees to adopt syn rather than anti conformation as in Watson-Crick base pairs. There is growing evidence that Hoogsteen base pairs play important roles in DNA replication, recognition, damage or mispair accommodation and repair. Here, we constructed a database for existing Hoogsteen base pairs in DNA duplexes by a structure-based survey from the Protein Data Bank, and structural analyses based on the resulted Hoogsteen structures revealed that Hoogsteen base pairs occur in a wide variety of biological contexts and can induce DNA kinking towards the major groove. As there were documented difficulties in modeling Hoogsteen or Watson-Crick by crystallography, we collaborated with the Richardsons’ lab and identified potential Hoogsteen base pairs that were mis-modeled as Watson-Crick base pairs which suggested that Hoogsteen can be more prevalent than it was thought to be. We developed solution NMR method combined with the site-specific isotope labeling to characterize the formation of, or conformational exchange with Hoogsteen base pairs in large DNA-protein complexes under solution conditions, in the absence of the crystal packing force. We showed that there are enhanced chemical exchange, potentially between Watson-Crick and Hoogsteen, at a sharp kink site in the complex formed by DNA and the Integration Host Factor protein. In stark contrast to B-form DNA, we found that Hoogsteen base pairs are strongly disfavored in A-form RNA duplex. Chemical modifications N1-methyl adenosine and N1-methyl guanosine that block Watson-Crick base-pairing, can be absorbed as Hoogsteen base pairs in DNA, but rather potently destabilized A-form RNA and caused helix melting. The intrinsic instability of Hoogsteen base pairs in A-form RNA endows the N1-methylation as a functioning post-transcriptional modification that was known to facilitate RNA folding, translation and potentially play roles in the epitranscriptome. On the other hand, the dynamic property of DNA that can accommodate Hoogsteen base pairs could be critical to maintaining the genome stability.