Past Seminars

Abstract:
We shall discuss several approximations and computational algorithms that are useful in the analysis of key performance measures that arise in applied settings such as insurance risk and queueing. Some examples of the types of performance measures that we shall consider are ruin probabilities in the insurance context, which can be used as ruin management tools, and time-in-system characteristics in queueing theory, which are crucial in the analysis and design of waiting lines.

In the first part of the talk we will briefly discuss several limit theorems, including corrected diffusion approximations and large deviations asymptotics, for the analysis of performance measures such as those indicated in the previous paragraph. These approximations generalize and extend important results in the literature. It is often the case that limit theorems provide more than just asymptotic approximations to certain quantities of interest. In the second part of the talk we will present rare event simulation methodology that is based on the analytic insights obtained from results described in the first part of the talk. The computational procedures that we shall discuss are state-dependent importance sampling algorithms that can be proved to be efficient in a precise mathematical sense.

Abstract:
Cartwright and Littlewood discovered chaotic solutions in the periodically forced van der Pol equation in the 1940's. Subsequent work by Levinson, Levi and others has made this singularly perturbed system one of the archetypical dissipative systems with chaotic dynamics. Despite the extensive history of this system, many questions concerning its bifurcations and chaotic dynamics remain.

We use a combination of analysis of the singular limit and numerical simulation to describe a horseshoe map that arises in the three-dimensional phase space. The phenomenon of canards--trajectories that remain close to an unstable slow invariant manifold for a long time--play a crucial role in the analysis.

Abstract:
Constraint satisfaction problems are generalizations of CNF boolean formulas. We are given a set of variables, and a domain of values that the variables can take. Some subsets of the variables have "constraints" which restrict the value-assignments that can be made to those variables. A problem is satisfiable if there is an assignment of values to the variables which does not violate any of the constraints. Some well-studied special cases are k-SAT, graph colourability and graph homomorphism.

In this talk, we discuss models of random constraint satisfaction problems. The main issue is the following: if we form a random problem by adding random constraints one-at-a-time, how does the probability of the problem being satisfiable change? It is clear that this probability
is monotonically decreasing as the number of constraints increases, but how suddenly does it decrease? How many constraints must be added before the decrease is significant? (In formal terms, these questions can be rephrased as "does the problem have a sharp threshold of satisfiability?" and "how many constraints must be added before it is no longer almost surely satisfiable?") These questions generalize the well-studied notions of the threshold of satisfiability for a random instance of k-SAT and the threshold of k-colourability for a random graph.

Abstract:
The logical framework Twelf provides an experimental platform to specify, implement and execute formal systems. One of its applications is in proof-carrying code and proof-carrying authentication, where it is successfully used to specify and verify formal guarantees about the run-time behavior of programs. These real-world applications have exposed some critical bottlenecks: execution of many logical specifications is severely hampered and some are not executable at all, thereby limiting its application in practice.

In this talk, I will describe three optimizations which substantially improve the performance and extend the power of the existing system. First, I give an optimized unification algorithm for logical frameworks which allows us to eliminate unnecessary occurs-checks. Second I present a novel execution model based on selective memorization and third I will discuss term indexing techniques to sustain performance in large-scale examples. As experimental results will demonstrate, these optimizations taken together constitute a significant step toward exploring the full potential of logical frameworks in real-world applications.

Abstract:
Given a sequence of independent random variables, how close is their sum to its mean? The answer is that it is exponentially close, assuming that the random variables are well-behaved. Some explicit bounds are known under several reasonable assumptions on the random variables. We describe here well-known exponential tail bounds that are relevant to computer science. These are organized in the following categories:

(a) standard bounds: Chernoff and Hoeffding bounds.
(b) martingale bounds: McDiarmid's bound and Azuma's inequality.
(c) isoperimetric bound: Talagrand's inequality.

We survey the basic ideas behind these bounds and describe the most direct proofs. Then, we observe a simple quantitative connection between Chernoff-Hoeffding bounds and the notion of negatively associated random variables.

Abstract:
Interested in learning about an open source alternative to Microsoft's oft-delayed WinFS, Google's recently announced desktop search system, or Apple's Spotlight search technology? Would you find it useful if your computer held on to extra information about your files so you could locate them with greater ease?

I have implemented my own approach to metadata storage and search that parallels the functionality found in these systems. This includes a method for reliably storing additional information about your files seamlessly and quickly. Furthermore, my approach is unlike those commercial solutions because it is extremely portable across operating systems, underlying file systems, and database implementations.

Come to New Snell Hall room 175 Wednesday, December 8, 9:30 – 11:30 a.m. to hear more about the E.D.E.N. system architecture, discussion about keeping stored metadata in synchronization with actual files on disk (a.k.a. the coherence problem), and the interesting advances in search it can facilitate. The talk should be fairly complete, and accessible to anyone with basic interest in the subject matter.

Abstract:
Boosting is a widely successful approach to classification in which a number of "base classifiers" are incorporated into an aggregate classifier. The behavior of boosting seemed to run counter to the common view that a learning algorithm should strike a balance between the complexity of a hypothesis and its fit to the data. The influential "margin analysis" provided one explanation of this phenomenon.

Microarrays allow scientists to measure the rate of expression of a large number of genes simultaneously in a given tissue sample. These rates are referred to collectively as an expression profile for the tissue sample. Some biological problems can be addressed by learning a classifier for expression profiles.

Applying boosting, and some related algorithms, on microarray data, and related data, exposes that the margin analysis provides an incomplete explanation of generalization in boosting. Examining how suggests an alternative mode of analysis — we have carried out a preliminary analysis of this type. Suitably modified, boosting appears to be a useful tool for classifying expression profiles. (This talk includes joint research with Vinsensius Vega and Sanjoy Dasgupta.)

Abstract:
A square matrix D of size N is called 'unistochastic' if there exist a unitary U such that D_ ij=|U_ij|^2. Such matrices play important role in various quantum mechanical problems and we investigate their spectral properties.

We analyze the set V N of all unistochastic matrices of size N, which forms a subset of the Birkhoff's polytope - the set of all bistochastic (doubly stochastic) matrices of the same size. A complete characterization of the structure of V_2 and V_3 is presented, while for higher N only partial results are found .

Abstract:
A small group of actors in a large communication network is planning a terrorist act against people they disagree with. They are very careful in three ways:

• they take time to plan all details, to guarantee their "success";
• all their messages are well camouflaged: the context is encrypted so that it is difficult for an outsider to discern their real meanings; and
• the group members do not trust any outsider with the details of the plan and preparation.

Do we have any chance of discovering this group before they start implementing whatever they are planning? We describe models and efficient algorithms for detecting groups, functioning in communication networks, which attempt to hide their functionality–hidden groups. As expected, we find that if the background communications are dense or more structured, then the hidden group is harder to detect. Surprisingly, we also find that when the hidden group is non-trusting, it is easier to detect that group.

• Friday, September 10, Noon – SC 346
• Monday, September 13, Noon – SC 346
• Tuesday, September 14, 2:30 – 3:30 p.m. – SC 354
• Wednesday, September 15, Noon – 1 p.m. – SC 342
• Thursday, September 16, 2:30 – 3:30 p.m. – SC 354

Abstract:
A symmetric matrix is called degenerate by physicists if it has a multiple eigenvalue. Wigner and von Neumann have shown long ago that the degenerate matrices form a variety of codimension two in the space of all symmetric matrices. This explains the phenomenon of "avoidance of crossing". On the other hand the degenerate matrices are characterized by the single equation discr(S)=0, where discr(S) is the discriminant of S. In this talk we investigate the nature of the discriminant, especially its representation as a sum of squares.

In the second part it will be shown that some pencils of real symmetric matrices always contain a degenerate one.

Abstract:
The ability to effectively control a fluid would enable many exciting technological advances, including the design of quieter, more efficient aircraft. Most of the flow control strategies tried so far have been largely ad hoc, and have not used many of the available tools from control theory and dynamical systems, which can guide controller design as well as placement of sensors and actuators. These tools require knowledge of a model of the system in terms of a system of differential equations, and the equations governing a fluid, though known, are too complex for these tools to apply. This talk addresses model reduction techniques, which are used to simplify existing models, to obtain low-order models tractable enough to be used for analysis and control, while retaining the essential physics. These techniques provide a bridge between complex problems and the mathematical tools useful for their analysis.

Specifically, the talk will focus on recent developments of two techniques, Proper Orthogonal Decomposition (POD) and balanced truncation. Each of these techniques has strengths and weaknesses, and we show how ideas from both techniques may be combined, to exploit their strengths. We illustrate the methods by obtaining reduced-order models for a compressible flow past a cavity, and an incompressible channel flow.

Abstract:
Security is a major issue in today's networks. Passwords and private messages sent across the network are not as secure as one might expect. Although encryption schemes are available, the performance of applications that uses them are proven to be worst than those that do not use any encryption scheme. This thesis analyzes the standard RSA encryption algorithm and compares it with Fiat's Batch RSA algorithm. The two algorithms will be compared in a secure Server/Client Handshake Protocol. Our goal is to test Batch RSA and show that the standard Handshake Protocol can be improved with Batch.

Abstract:
We consider the problem of stochastic flow of multiple particles traveling on a closed loop, with a constraint that particles move without passing. We use a Markov chain description that reduces the problem to a generalized random walk on a hyperplane (with boundaries). By expressing positions via a moving reference frame, the geometry of the no-passing criteria is greatly simplified, with the resultant condition expressible as the coordinate system planes which bound the first orthant. To determine state transition probabilities, we decompose transitions into independent events and construct a digraph representation in which calculating transition probability is reduced to a shortest path determination on the digraph. The resultant decomposition digraph is self-converse, and we exploit that property to establish the necessary symmetries to find the stationary density for the process.

Abstract:
Image restoration is the process of minimizing or removing degradations from an observed image, which may be distorted by such things as blurring and noise. Such problems arise in applications ranging from microscopy to astronomy. Computational methods for restoring the image require solving large, very ill-conditioned linear systems. The structure of the "blurring" matrix determines whether it is feasible to use matrix factorizations, or whether iterative methods are more appropriate for solving the linear systems. In this talk we describe some aspects of image restoration algorithms, and show that the blurring matrix can often be represented in terms of Kronecker products. We also show how to exploit the Kronecker product structure to improve computational efficiency. Examples from various applications will be presented.

Abstract:
I will discuss some of the security holes in Internet protocols a various layers in the network protocol stack from application level protocols to link layer protocols. I will also discuss defenses that can be implemented at each layer. I will also discuss some of the most common classes of attacks on computer systems.

Abstract:
This talk focuses on bifurcation dynamics in control systems, which are described by ordinary differential equations, partial differential equations and delayed differential equations. In particular, bifurcations related to double Hopf, combination of double zero and Hopf, and chaos are presented. Center manifold theory and normal form theory are applied to simplify the analysis. Explicit stability conditions are derived and routes of Bifurcations leading to various complex dynamics are given. A system with time delayed feedback control is studied to show that time delay plays an important role in controlling and anti-controlling chaotic motions. Furthermore, a simple feedback controller is designed for anti-controlling Hopf bifurcation arising in the Lorenz system.

Abstract:
Last fall the University of Calgary offered a course on computer viruses and malicious software, the first of its kind in Canada and one of only a handful that have ever been offered worldwide. The course generated a global stream of controversy and media attention, in part because students were taught how to write viruses as well as defend against them.

This talk will be the first public presentation about the course. I will talk about the rationale behind the course, what I taught the students, how we put together a secure laboratory for coursework, and the experience we gained.

Abstract:
The ability to effectively control a fluid would enable many exciting technological advances, including the design of quieter, more efficient aircraft. Most of the flow control strategies tried so far have been largely ad hoc, and have not used many of the available tools from control theory and dynamical systems, which can guide controller design as well as placement of sensors and actuators. These tools require knowledge of a model of the system in terms of a system of differential equations, and the equations governing a fluid, though known, are too complex for these tools to apply. This talk addresses model reduction techniques, which are used to simplify existing models, to obtain low-order models tractable enough to be used for analysis and control, while retaining the essential physics. These techniques provide a bridge between complex problems and the mathematical tools useful for their analysis.

Specifically, the talk will focus on recent developments of two techniques, Proper Orthogonal Decomposition (POD) and balanced truncation. Each of these techniques has strengths and weaknesses, and we show how ideas from both techniques may be combined, to exploit their strengths. We illustrate the methods by obtaining reduced-order models for a compressible flow past a cavity, and an incompressible channel flow.

Abstract:
A popular method of encoding chaotic time-series from a physical experiment is the "threshold crossings" technique, relative to an arbitrary partition. The intent of symbol dynamics is to describe a dynamical system, but only a generating partition is expected to uniquely encode trajectories. We rigorously investigate some consequences of using itineraries relative to a nongenerating partition. We find the misrepresentation can be severe, including diminished topological entropy (but devil's staircase-like and surprisingly nonmonotone), and a high degree of nonuniqueness.

Abstract:
This thesis analyzes the causes of Internet Security problems and the advantages and disadvantages of the commonly used network security techniques such as encryption, authentication, secure protocols and firewall. It also introduces basic concepts and functions of firewall, and then analyzes the implementation price and security performance of firewall system with different architectures. It is important to research on firewall techniques because of its effective protection for network security.

Since proxy firewall is proved securer than packet filtering firewall, this system is designed as a proxy firewall. This system runs on a bastion host with Redhat Linux operation system. It has the abilities of Network Address Translator, internal information hide, strong user authentication, detailed log, etc. It is sufficient for normal Internet connection.

The focus of the thesis is on implementation of a mini type proxy firewall system, which includes a telnet proxy, an ftp proxy, user authentication service, log, and accounting. Telnet proxy tn-gw and ftp proxy jftpgw control telnet and ftp connection, respectively. They validate the connection, conduct the necessary user authentication, forward data between client and server, log necessary information and take down accounting data. User authentication service authsrv controls access in user instead of IP address thus makes system securer. It supports UNIX password and One-Time Password, with client embedded in proxies, sever creates challenge and verifies response, and user information is managed by a manage program. Detailed log is used for future audit and trace, and accounting data is used for calculating communication fee. Total incoming and outgoing bytes and online time for E-mail application are calculated by user name, while those for other applications are calculated by user name or IP address, and all are done automatically every month.

With consideration of the development of network and security technology, this thesis has also studied on the new firewall techniques and some improvement need to make that might be considered in future firewall design.

Abstract:
The Pigeonhole Principle states that if n pigeons are placed in n-1 holes, then at least one hole will contain more than one pigeon. The Weak Pigeonhole Principle refers to a version where the number of pigeons is significantly larger than the number of holes, typically at least twice as large. Both of these basic principles have numerous applications.

These theorems are easy to prove. How easy? Questions about the complexity of proving mathematical theorems are natural but they also have connections to important problems in computational complexity, automated theorem proving and software verification.

In this talk, we will introduce the study of proof complexity and present one of the simplest known proofs of the Weak Pigeonhole Principle. This is joint work with Toni Pitassi and Alan Woods.

Abstract:
Evolutionary histories, or phylogenies, form an integral part of much work in biology. In addition to the intrinsic interest in the interrelationships between species, phylogenies are used for drug design, multiple sequence alignment, and even as evidence in a recent criminal trial. Much work has been done on designing algorithms that build phylogenetic trees given representative sequences of their DNA. The optimization criteria preferred by biologists for building trees is NP-hard. So, heuristics are often used that return many possible trees, instead of single optimal tree. This talk concentrates on the heuristics used for tree reconstruction, as well as how to summarize, analyze, and visualize these sets of trees. In particular, we will focus on fast reconstruction methods with provably nice properties, calculating biologically meaningful distances between trees quickly, and visualizing large sets of trees using the treecomp package designed by our group, as a module for the Mesquite system (developed by Wayne and David Maddison).

Abstract:
Many undergraduate algorithms courses and texts often organize the material in terms of "algorithmic paradigms," such as greedy algorithms, backtracking, dynamic programming, local search, primal-dual, etc. We seem to be able to intuitively describe what we have in mind when we discuss these classes of algorithms but rarely (if ever) do we (or any of the standard texts) attempt to define precisely what we mean by greedy, dynamic programming, etc.

In a paper co-authored with Nielsen and Rackoff, we proposed a definition for greedy-like (approximation) algorithms, called priority algorithms. We did so in the context of classical scheduling problems. Angelopoulos and Borodin then applied the priority algorithm framework to the facility location and set cover problems. Impagliazzo and Davis have recently applied the framework to a number of traditional graph theoretic optimization problems.

Similar to online algorithms, we want to derive limitations on the (approximation) power of priority algorithms based only on the structure of the algorithm (allowing unbounded time complexity). Hopefully such a study will also lead to new algorithms. We motivate the priority algorithm framework by discussing some well known greedy algorithms and the corresponding lower bounds provable within this framework. We also discuss some extensions of the model such as the "one-pass" framework of Erlebach and Spieksma.

Abstract:
The hype of the Internet boom has faded. But the challenges of how to drive business value from technology investments are more critical now than ever before. Products will be built only when ordered. Orders will automatically trigger a ripple effect across your business, from billing to manufacturing to shipping. Whatever you deliver, whether it's products to consumers, information to employees, or parts to a factory halfway around the world will need to be coordinated through a technology backbone that makes the most of tightly integrated, streamlined critical business processes.

Enter the new world of "e-business on Demand". A place where it's not just being on the Net but being a part of it, with the ability to respond with speed to any customer demand, market opportunity or competitive threat. To meet this challenge, Grid Computing has emerged as an enabling technology that forms the foundation of the "on-demand" computing environment. Grid Computing is a new, services oriented architecture based on "Open Grid Services Architecture" (OGSA) that embraces heterogeneous systems and involves distributed computing-over the Internet or any private network-via open standards. It is designed to help businesses efficiently consolidate, pool, share and manage IT resources.

Come learn about how Grid Computing helps:

• manage resources across distributed heterogeneous platforms
• deliver seamless Quality of Service (QoS) across integrated Grid resources
• define open, published interfaces
• integrate with existing IT resources

Abstract:
Numerical calculations of two-dimensional viscous incompressible flow induced by an impulsively started circular cylinder which performs rotational and/or rectilinear vibrations are reported at Reynolds number $R=855$. These oscillations are harmonic and superimposed on the constant translational velocity to examine the effect of increase of the oscillation frequency on the near-wake structure and the hydrodynamic forces acting on the cylinder. The numerical results lead to the postulation of asymmetric and symmetric vortex shedding regimes depending on the oscillation conditions, which are discussed in some detail for exemplary cases. Comparisons are made with previous existing results to validate the solution methodology.

Abstract:
We consider a wide class of anisotropic optimal trajectory problems, review the dynamic programming approach and derive the corresponding static Hamilton-Jacobi-Bellman PDE. A usual numerical approach requires some discretized version of the PDE to be satisfied at every mesh point, thus leading to a necessity to solve a coupled system of N nonlinear equations. Ordered Upwind Methods (OUMs) present an alternative (non-iterative) approach to obtaining the convergent numerical solution. These methods are based on a careful use of the direction of information propagation, stemming from the Optimality Principle. The resulting computational complexity is O(N log N) on any unstructured mesh with N mesh points.

We illustrate OUMs on several continuous & hybrid optimal trajectory test-problems. In addition, we briefly describe applicability of OUMs to problems in anisotropic front propagation, in optimal control under uncertainty, and in dynamical systems. Several of the above projects are joint work with J.A. Sethian and with J. Guckenheimer.

Abstract:
Oriented matroids are a combinatorial abstraction of linear algebra. They are a natural concept which has applications in areas like topology, combinatorics and algebraic geometry to name a few. In this talk I will introduce oriented matroids by using points, vectors and lines on the plane. As an example we will use oriented matroids to read off the faces of a high dimensional polyhedron. This talk is accessible to undergraduates. However some knowledge of linear algebra is required. (Students interested in pursuing a Ph.D. are particularly encouraged to talk with the speaker.)

Abstract:
Many diseases, such childhood diseases, dengue fever, and West Nile virus, appear to oscillate randomly as a function of seasonal environmental or social changes. Such oscillations appear to have a chaotic bursting character, although it is still uncertain how much is due to random fluctuations. Such bursting in the presence of noise is also observed in driven lasers. In this talk, I will show how noise can excite random outbreaks in simple models of seasonally driven outbreaks, as well as lasers. The models for both population dynamics will be shown to share the same class of underlying topology, which plays a major role in the cause of observed stochastic bursting. Finally, I will speculate on some ideas of stochastic epidemic control, and how to test these ideas in a physical optics experiment.

Abstract:
Then we look out on a clear night, the universe seems infinite. Yet this infinity might be an illusion. During the first half of the presentation, computer games will introduce the concept of a "multiconnected universe". Interactive 3D graphics will then take the viewer on a tour of several possible shapes for space. Finally, we'll see how satellite data released in February 2003 are beginning to reveal the true shape of our universe. The only prerequisites for this talk are curiosity and imagination. For first-year students on up.

Abstract:
Splines have many uses in industry, ranging from process control contexts to research and development. While splines are often seen as functions of one variable, there are also uses for higher dimensional splines. (You may even be making use of 3d splines and never know it.) In this talk I'll sample some of these uses, I'll also suggest why we have used a particular class of spline model as opposed to some other model form.

Abstract:
A graph is said to be intrinsically knotted if it contains a knotted cycle in every (tame) spatial embedding. Similarly, a graph is said to be intrinsically 3-linked if it contains a non-split 3 component link in every spatial embedding. It is an open question to determine all "minor-minimal" intrinsically knotted (or intrinsically 3-linked) graphs. We will discuss recent results concerning this open question. Some of the results discussed represent work done jointly with Garry Bowlin. No prior knowledge of knot theory will be assumed.

Abstract:
This talk will present the mathematical properties and applications of a recently introduced technique of extraction of nonstationary sinusoidal signals and estimation of their parameters, namely amplitude, phase and frequency. The nonlinear dynamical system governing the algorithm presents open stability problems, which will be discussed in this presentation. An outline of applications of the technique in biomedical engineering, nondestructive testing of materials and power engineering will be presented.

Abstract:
In this talk I introduce the mathematics involved in the variational approach to image analysis, comment on the connections to robust statistics and discuss in some detail one particular image denoising model: the Rudin-Osher-Fatemi Total Variation minimization method. The talk is expository in nature and will be friendly to graduate students. I will also comment on our most recent results.

Abstract:
Ad hoc wireless networks are a relatively new field, and as they gain more popularity, various new applications are bound to use them because of several reasons. In a network, the Medium Access Control (MAC) protocols are responsible for enabling the communication between two nodes. In a wireless network, however, these protocols gain even more importance since the communication channel is inherently prone to errors and unique problems like those caused by hidden terminals and signal fading effects. Although a lot of research has been conducted on MAC protocols, the various issues involved have mostly been presented in isolation of each other. We therefore make an attempt to present a comprehensive review of several schemes, integrating the various related issues and challenges with a view to providing a big-picture outlook to this vast area. We present a classification of MAC protocols based on their operation principles and underlying features. We look at the aspect of Quality of Service (QoS) in the context of Ad hoc wireless networks, and attempt to correlate the challenges involved with suitable approaches presented in the literature. We also consider the unique application of Sensor Networks, and review some solutions that have been presented in this regard. In conclusion, we present a brief summary of key ideas and a general direction for future work.

Abstract:
Qualitative properties of numerical solutions of ordinary differential equations (ODEs) attracted a lot of attention recently. It was shown that classical numerical methods for solving ODEs are very poor at preserving invariants. Linear multistep formulas can preserve only linear invariants, while some of the implicit Runge-Kutta methods can preserve also quadratic invariants.

The term Geometric integrator means a method that is designed not just to minimize (in the classical sense) the numerical error but also to render correctly the invariants (i.e. the geometry) of the solution.

Since an invariant of an ODE can be interpreted as a homogeneous space of some Lie group, the natural environment for investigating invariant-preserving numerical methods for ODEs is the framework of Lie groups. If we know how to retain Lie-group invariance under discretization, we can also keep the solution on the homogeneous space.

We will review briefly recent advances in numerical methods that advance solutions of ODEs on Lie groups. In particular we will mention Runge-Kutta Munthe-Kaas methods for solving general nonlinear ODEs and Magnus methods for the solution of linear ODEs.

Abstract:
Multimedia on the Internet has become not only a reality but also a necessity in the Web's appeal to millions of users, and the lack of effective end-to-end service (QoS) in such applications is now a cause for significant concern. In addition, the heterogeneity of the networks and end systems makes it difficult to multicast Internet multimedia in an efficient and flexible way. The interaction between multicasting and the delivery of multiple time-correlated continuous media streams with real-time delay requirements poses various new and interesting problems in research on communication protocols and architectures.

We propose a novel resource reservation mechanism, Dynamic Management of QoS with Priority (DMQP), for multimedia multicasting over the Internet. DMQP is a resource reservation based approach to provide QoS guarantee for real-time data traffic, in which an application requests QoS by specifying a range of values and the network tries to provide service at a specified point within this range depending upon its service class. DMQP achieves the service differentiation by classifying the end-users into two classes : normal user and prioritized user.

Abstract:
In the thesis I explore a new approach to solving the E-unification problem, i.e., the problem of solving equations modulo an equational theory presented as a set of identities.

This approach is goal-directed, because it searches for a solution for an equation by analyzing the structure of the goal (the equation to be solved), as opposed to procedures based on a completion of an equational theory. It is top-down, since it analyzes the goal and applies inference rules to the goal only with respect to the top symbols in the terms in the goal equation.

Such a goal-directed, top-down procedure is shown to be a complete, semi-decision procedure.

Next I will examine different ways of putting syntactic restrictions on a presentation of an equational theory, so that this semi-decision procedure becomes a decision procedure (it always terminates).

Hence we are able to prove complexity results for E-unification in several classes of equational theories.

Abstract:
Network management systems (NMS) have played an important role in today's telecommunication network. Now telecommunication network environments have become more complicated, and heterogeneous devices are provided by different vendors. What is more, the amount of network devices is rapidly increasing. These trends require NMS to provide standard interfaces to share information and be scalable to manage complex networks. This paper presents a method to design an open, standards-based and distributed NMS with Common Object Request Broker Architecture (CORBA). CORBA facilitates the inter-communication among different NMS. Also CORBA's inherent distributed capability makes it possible to manage large-scale networks. Obviously, for a lot of devices, a single server is not enough to host the NMS. Here I propose an efficient algorithm to divide the managed system into partitions and distribute every partition to each server. This way, each server will hold an equivalent workload. At the same time, this method tries to reduce server-server communication. The basic principle here is based on heuristic optimization strategy.

Abstract:
XML (eXtensible Markup Language) is fast emerging as the dominant standard for representing and exchanging information over the Internet. However, for the foreseeable future, a significant amount of business data will continue to be stored in the relational database system. It is necessary to be able to extract relational data from XML documents and store it in a database, as well as to generate XML documents from known databases. We build two frameworks XML Generator and X2R to solve the following problems: 1) Generating XML document and DTD from relational schema, 2) Mapping relational schema from an XML document with DTD.