In 1931 Kurt Godel proved that there is no (recursively enumerable) set of axioms that capture the first order properties of the integers with respect to =, + and multimplication. In this talk we outline a slightly weaker version of the theorem in which exponentiation is included among the integer operations.
Brief definitions of formal systems and proofs will be given, and a set NT of axioms for number theory will be introduced. Methods are developed for encoding configurations of a Turing machine as numbers, and for encoding halting computations of a Turing machine as numerical expressions. It is then proved that unsatisfiable sentences and sentences provable from NT are recursively inseparable. Finally, generalizing from NT it is shown that there is no (recursively enumerable) set of axioms that is complete for number theory.
Modeling and predicting RNA secondary structures with pseudoknots remains an important problem in computational biology. The Parallel Communicating Grammar System proposed by Cai et al. allows the development of a full probabilistic model for sequence prediction and profiling. However, the prediction algorithm based on this model may only be applied to sequences of less than 100 nucleotides due to its exceptionally large space complexity. A new algorithm that requires significantly less memory has been developed. Experiments show that this new algorithm can yield excellent prediction results (with an accuracy of 86%) on sequences intractable for the original optimal algorithm (up to 204 nucleotides) with reasonable computational resource requirements.
The problem is to find out if it is possible to travel from one prescribed vertex to another in a graph when one is severely limited in memory. Our emphasis will be to explain some of the essential ideas in two recent advances on this problem, [Nisan, Szemeredi, Wigderson: citeseer.nj.nec.com/233520.html] and [Armoni, Ta-Shma, Widgerson, Zhou : JACM 47]
The purpose of this presentation is to give the audience a general understanding of different algorithms that could be used for AI in Video games, and to also explain some of the things that these algorithms could be used for.
In this talk we will prove that if P=NP then EXP=NEXP. This can be generalized to the following: If TIME(f(n)) = NTIME(f(n)), then TIME(g(f(n))) = NTIME(g(f(n))), where f(n) >= n and g(n) >= n for all sufficiently large n. We will also introduce two NEXP-complete problems: "SUCCINCT CIRCUIT SAT" and "SCHONFINKEL-BERNAYS SAT".
To show that EXACT TSP is DP-Complete, we will first introduce and establish the DP-completeness of the language SAT-UNSAT, then obtain a reduction from SAT-UNSAT to EXACT TSP.
Stochastic context free grammars are used to model RNA secondary structures. Inside-Outside Algorithm (Lari & Young, 1990) estimates the parameters associated with the rules in the grammar with a large time and memory complexity. We introduce genetic algorithms to solve the same problem with its flexibility and simplicity.
The following exercise is typical in introductory texts on deterministic finite automata (DFAs): "produce an automaton that recognizes the set of binary strings that, when interpreted as binary numbers, are divisible by k." The traditional (and correct) answer builds a k-state automaton that keeps track not only of divisibility by k, but also the current residue modulo k. Unfortunately, the traditional answer in general fails to produce a minimal DFA. We will present and prove a theorem answering the question "how many states DOES a minimal DFA recognizing the set of base-b numbers divisible by k have?" (Hopefully, also, "what does it look like?")
The success of parallel computers is highly dependent on their underlying interconnection network(IN). The IN must effectiviely disseminate information among its processors. In this talk, we'll look at the symmetry in interconnection networks based on Cayley graphs of permutation groups. An efficient neighbourhood broadcasting scheme is then introduced for the star interconnection network.
References:
1. S. Lakshmivarahan, Jung-Sing Jwo and S.K. Dhall. Symmetry in interconnection networks based on Cayley graphs of permutation groups. (Parallel Computing, 19:361-407, 1993.)
2. Neighbourhood broadcasting scheme for star interconnection networks. I.M.Mkwawa, D. D. Kouvatsos.
This talk introduces a novel Genetic Algorithm method for solving multi-objective optimization problems using reduced models. Our method, called Objective Exchange Genetic Algorithm for Design Optimization (OEGADO), is intended for solving real-world application problems. For such problems the number of objective evaluations performed is a critical factor as a single objective evaluation can be quite expensive. The aim of our research is to reduce the number of objective evaluations needed to find a well-distributed sampling of the Pareto-optimal region by applying reduced models to steady state multi-objective GAs. OEGADO runs several GAs concurrently with each GA optimizing one objective and forming a reduced model of its objective. At regular intervals, each GA exchanges its reduced model with the others. The GAs use these reduced models to bias their search towards compromise solutions. Empirical results in several engineering and benchmark domains comparing OEGADO with two state-of-the-art Multi-Objective Evolutionary Algorithms show that OEGADO outperformed them for difficult problems.
I am currently working with Dr.Rasheed on this topic.
Noncoding RNAs are biologically important and may play indispensable roles in the regulating processes for a biological entity. It is thus desirable to develop search tools for homologies of non-coding RNA sequences in sequence databases. However, unlike coding RNA sequences whose nucleotides provide information for protein generation, the functionalities of a non-coding RNA sequence are mainly determined by the secondary structures that it folds into. The most commonly used search tools (BLAST, FASTA etc) for homologies only compare the content of sequences using pairwise alignment and hence may fail to detect sequences that are similar in structure but considerably different in content.
To efficiently incorporate structural information into the alignment of sequences and compute the simliarity of their structures, E. Rivas and S. Eddy developed three statistical models for pairwise alignments between position-independent, coding and non-coding sequences. A pairwise alignment can thus be classified into any of the three categories based on the the computed posterior probabilities. Experiments have shown that this approach can efficiently detect non-coding RNAs with a fair degree of reliability and possibly be combined with BLASTN to find new non-coding RNA genes.
Stochastic context-free grammars (SCFGs) are applied to the problems of folding, aligning and modeling families of RNA sequences. SCFGs capture the sequences' common primary and secondary structure. They are a method of characterizing biological sequences that take into account the statistical identity of different sequence positions including pairwise interactions between positions.
There is a need to build a tool for the generation of SCFG grammars for pseudoknots(and other simple structures) from aligned RNA seqeuences of known structures. This would reduce human labor substantially, as it is cumbersome to write a grammar manually by hand for a sequence, and would also help in the probabilistic analysis of sequences.
Stochastic context free grammars have been widely used for RNA secondary structure prediction. The CYK (Cocke-Younger-Kasami) algorithm uses dynamic programming to determine the most likely RNA folding structure, but much run time is spent for calculating a 3-D matrix. We found that some of the cells in the 3-D matrix are not needed, and some of cells may be useless. We introduce a method to reduce the number of such cells which are calculated, and thus improve the running time.
Cryptography deals with the situation that two parties wish to communicate in the presence of malevolent eavesdroppers. In the presentation, the following topics are discussed:
1. Shared key cryptography scheme is presented and disadvantages are shown
2. Public-Key Cryptography scheme is introduced, then the definition of one-way function is explained and three examples of one-way functions are discussed. The RSA function is discussed in detail.
3. Cryptography and complexity are discussed in relation to the classes P, UP and NP. The theorem that UP = P iff there are no one-way functions is introduced.
4. Finally, randomized cryptography is proposed briefly.
|
| CATS |