This thesis concerns combinatorics on words. I present many results in this area, united by the common themes of periodicity and repetition. Most of these results have already appeared in journal or conference articles. Chapter 2 &ndash; Chapter 5 contain the most significant contribution of this thesis in the area of combinatorics on words. Below we give a brief synopsis of each chapter. Chapter 1 introduces the subject area in general and some background information. Chapter 2 and Chapter 3 grew out of attempts to prove the Decreasing Length Conjecture (DLC). The DLC states that if &prime; is a morphism over an alphabet of size <em>n</em> then for any word <em>w</em>, there exists 0 &le; <em>i</em> < <em>j</em> &le; <em>n</em> such that |&prime;<em>i</em>(<em>w</em>)| &le; |&prime;<em>j</em>(<em>w</em>)|. The DLC was proved by S. Cautis and S. Yazdani in <em>Periodicity, morphisms, and matrices</em> in <em>Theoret. Comput. Sci. </em> (<strong>295</strong>) 2003, 107-121. More specifically, Chapter 2 gives two generalizations of the classical Fine and Wilf theorem which states that if (<em>fn</em>)<em>n</em>&ge;0, (<em>gn</em>)<em>n</em>&ge;0 are two periodic sequences of real numbers, of period lengths <em>h</em> and <em>k</em> respectively, (a) If <em>fn</em> = <em>gn</em> for 0 &le; <em>n</em> < <em>h</em> +<em> k</em> - gcd(<em>h</em>;<em>k</em>), then <em>fn</em> = <em>gn</em> for all <em>n</em> &ge; 0. (b) The conclusion in (a) would be false if <em>h</em> + <em>k</em> - gcd(<em>h</em>;<em>k</em>) were replaced by any smaller number. We give similar results where equality in (a) is replaced by inequality and to more than two sequences. These generalizations can be used to prove weak versions of the DLC. Chapter 3 gives an essentially optimal bound to the following matrix problem. Let <em>A</em> be an <em>n</em> &times; <em>n</em> matrix with non-negative integer entries. Let <em>f</em>(<em>n</em>) be the smallest integer such that for all <em>A</em>, there exist <em>i</em> < <em>j </em>&le; <em>f</em>(<em>n</em>) such that <em>Ai</em> &le; <em>Aj</em>, where <em>A</em> &le; <em>B</em> means each entry of <em>A</em> is less than or equal to the corresponding entry in <em>B</em>. The question is to find good upper bounds on <em>f</em>(<em>n</em>). This problem has been attacked in two different ways. We give a method that proves an essentially optimal upper bound of <em>n</em> + <em>g</em>(<em>n</em>) where <em>g</em>(<em>n</em>) is the maximum order of an element of the symmetric group on <em>n</em> objects. A second approach yields a slightly worse upper bound. But this approach has a result of independent interest concerning <em>irreducible matrices</em>. A non-negative <em>n</em> &times; <em>n</em> matrix <em>A</em> is <em>irreducible</em> if &sum;{<em>i</em>=0}^{<em>n</em>-1}<em>Ai</em> has all entries strictly positive. We show in Chapter 3 that if <em>A</em> is an irreducible <em>n</em> &times; <em>n</em> matrix, then there exists an integer <em>e</em> > 0 with <em>e</em> = <em>O</em>(<em>n</em> log <em>n</em>) such that the diagonal entries of <em>Ae</em> are all strictly positive. These results improve on results in my Master's thesis and is a version of the DLC in the matrix setting. They have direct applications to the growth rate of words in a D0L system. Chapter 4 gives a complete characterization of two-sided fixed points of morphisms. A weak version of the DLC is used to prove a non-trivial case of the characterization. This characterization completes the previous work of Head and Lando on finite and one-sided fixed points of morphisms. Chapter 5, 6 and 7 deal with avoiding different kinds of repetitions in infinite words. Chapter 5 deals with problems about simultaneously avoiding cubes and large squares in infinite binary words. We use morphisms and fixed points to construct an infinite binary word that simultaneously avoid cubes and squares <em>xx</em> with |<em>x</em>| &ge; 4. M. Dekking was the first to show such words exist. His construction used a non-uniform morphism. We use only uniform morphisms in Chapter 5. The construction in Chapter 5 is somewhat simpler than Dekking's. Chapter 6 deals with problems of simultaneously avoiding several patterns at once. The patterns are generated by a simple arithmetic operation. Chapter 7 proves a variant of a result of H. Friedman. We say a word <em>y</em> is a <em>subsequence</em> of a word <em>z</em> if <em>y</em> can be obtained by striking out zero or more symbols from <em>z</em>. Friedman proved that over any finite alphabet, there exists a longest finite word <em>x</em> = <em>x</em>&#8321;<em>x</em>&#8322; &middot;&middot;&middot; x<em>n</em> such that x<em>i</em>x<em>i</em>i+1 &middot;&middot;&middot; <em>x</em>&#8322;<em>i</em> is not a subsequence of <em>xjxj</em>+1 &middot;&middot;&middot; <em>x</em>&#8322;<em>j</em> for 1 &le; <em>i</em> < <em>j</em> &le; <em>n</em>/2. We call such words <em>self-avoiding</em>. We show that if &#8220;subsequence&#8221; is replaced by &#8220;subword&#8221; in defining self-avoiding, then there are infinite self-avoiding words over a 3-letter alphabet but not over binary or unary alphabets. This solves a question posed by Jean-Paul Allouche. In Chapter 8 we give an application of the existence of infinitely many square-free words over a 3-letter alphabet. The <em>duplication language</em> generated by a word <em>w</em> is roughly speaking the set of words that can be obtained from <em>w </em>by repeatedly doubling the subwords of <em>w</em>. We use the existence of infinitely many square-free words over a 3-letter alphabet to prove that the duplication language generated by a word containing at least 3 distinct letters is not regular. This solves an open problem due to J. Dassow, V. Mitrana and Gh. Paun. It is known that the duplication language generated by a word over a binary alphabet is regular. It is not known whether such languages are context-free if the generator word contains at least 3 distinct letters. After the defence of my thesis I noticed that essentially the same argument was given by Ehrenfeucht and Rozenberg in <em>Regularity of languages generated by copying systems</em> in <em>Discrete Appl. Math. </em> (<strong>8</strong>) 1984, 313-317. Chapter 9 defines a new &#8220;descriptive&#8221; measure of complexity of a word <em>w</em> by the minimal size of a deterministic finite automaton that accepts <em>w</em> (and possibly other words) but no other words of length |<em>w</em>|. Lower and upper bounds for various classes of words are proved in Chapter 9. Many of the proofs make essential use of repetitions in words.

Hypermedia applications can be defined as collections of interactive multimedia documents that are organized as a hypertext net. The variety of application domains and the complexity of the relationship among the application components make the design and development of these hypermedia applications a difficult process. Hypermedia design models help designers to complete their conceptualization tasks, provide a conceptual understanding of hypermedia systems and defining the relationships among system components. However, when existing document models are used, features such as logging, error handling, access control and personalized view generation are notoriously difficult to implement in a modular way. The result is that the code related to these features is tangled across a system, which leads to quality, productivity and maintenance problems. In this thesis, we provided an aspect-oriented approach to design and develop hypermedia documents. A general aspect-based document model is defined to support the separation of concerns related to the features previously described. As a result, each feature is modularized as a different aspect and, in this way, the "tangling code" problem is solved. We have also applied the general document model in a concrete case study combining DOM and AspectJ. The resulting implementation provided a new prototype dealing with many features defined as aspects such as access control, logging, view generation, annotation and dynamic event handling.

This thesis applies modern financial option valuation methods to the problem of telecommunication network capacity investment decision timing. In particular, given a cluster of base stations (wireless network with a certain traffic capacity per base station), the objective of this thesis is to determine when it is optimal to increase capacity to each of the base stations of the cluster. Based on several time series taken from the wireless and bandwidth industry, it is argued that capacity usage is the major uncertain component in telecommunications. It is found that price has low volatility when compared to capacity usage. A real options approach is then applied to derive a two dimensional partial integro-differential equation (PIDE) to value investments in telecommunication infrastructure when capacity usage is uncertain and has temporary sudden large variations. This real options PIDE presents several numerical challenges. First, the integral term must be solved accurately and quickly enough such that the general PIDE solution is reasonably accurate. To deal with the integral term, an implicit method is suggested. Proofs of timestepping stability and convergence of a fixed point iteration scheme are presented. The correlation integral is computed using a fast Fourier transform (FFT) method. Techniques are developed to avoid wrap-around effects. This method is tested on option pricing problems where the underlying asset follows a jump diffusion process. Second, the absence of diffusion in one direction of the two dimensional PIDE creates numerical challenges regarding accuracy and timestep selection. A semi-Lagrangian method is presented to alleviate these issues. At each timestep, a set of one dimensional PIDEs is solved and the solution of each PIDE is updated using semi-Lagrangian timestepping. Crank-Nicolson and second order backward differencing timestepping schemes are studied. Monotonicity and stability results are derived. This method is tested on continuously observed Asian options. Finally, a five factor algorithm that captures many of the constraints of the wireless network capacity investment decision timing problem is developed. The upgrade decision for different upgrade decision intervals (e. g. monthly, quarterly, etc. ) is studied, and the effect of a safety level (i. e. the maximum allowed capacity used in practice on a daily basis&mdash;which differs from the theoretical maximum) is investigated.

Wireless infrastructure networks provide high-speed wireless connectivity over a small geographical area. The rapid proliferation of such networks makes their management not only more important but also more difficult. Denser network deployments lead to increased wireless contention and greater opportunities for RF interference, thereby decreasing performance. <br /><br /> In the past, wireless site surveys and simplified wireless propagation models have been used to design and configure wireless systems. However, these techniques have been largely unsuccessful due to the dynamic nature of the wireless medium. More recently, there has been work on dynamically configurable systems that can adapt to changes in the surrounding environment. These systems improve on previous approaches but are still not adequate as their solutions make unrealistic assumptions about the operating environment. Nevertheless, even with these simplified models, the network design and configuration problems are inherently complex and require tradeoffs among competing requirements. <br /><br /> In this thesis, we study a self-management system that can adjust system parameters dynamically. We present a system that does not impose any restrictions on the operating environment, is incrementally deployable, and also backwards compatible. In doing so, we propose, (i) framework for modeling system performance based on utility functions, (ii) novel approach to measuring the utility of a given set of configuration parameters, and (iii) optimization techniques for generating and refining system configurations to maximize utility. Although our utility-function framework is able to capture a variety of optimization metrics, in this study, we focus specifically on maximizing network throughput and minimizing inter-cell interference. Moreover, although many different techniques can be used for optimizing system performance, we focus only on transmit-power control and channel assignment. We evaluate our proposed architecture in simulation and show that our solution is not only feasible, but also provides significant improvements over existing approaches.

Due to the importance of plants in the Earth's ecosystem, their photobiological responses have become the subject of extensive research in life sciences. Leaf optical models have been developed to assist in the analysis of remotely sensed data to derive information on leaf biochemistry and anatomy from foliar spectral curves (transmittance and reflectance). In this paper, we investigate the implications of using in vitro pigment absorption spectra to model foliar optical properties in the visible domain. Typically pigment absorption spectra have been determined using light absorption spectroscopy or by applying a data fitting approach. Alternatively, we propose the use of photoacoustic absorption spectroscopy, which despite being available in the literature has not been used in the modeling of foliar optical properties before. We also perform computational experiments in which foliar modeled reflectance and transmittance spectral curves generated using these different absorption data sets are compared with actual measured data. Our findings indicate that the proposed alternative not only allows key pigments to be individually incorporated into the models, which, in turn, increases the predictability of the simulations, but also enables the generation of modeled leaf spectra that are closer approximations to measured leaf spectra than those obtained using absorption data derived from standard absorption spectroscopy procedures.

Database management systems (DBMSs) have been used successfully in traditional business applications that require persistent data storage and an efficient querying mechanism. Typically, it is assumed that the data are static, unless explicitly modified or deleted by a user or application. Database queries are executed when issued and their answers reflect the current state of the data. However, emerging applications, such as sensor networks, real-time Internet traffic analysis, and on-line financial trading, require support for processing of unbounded data streams. The fundamental assumption of a data stream management system (DSMS) is that new data are generated continually, making it infeasible to store a stream in its entirety. At best, a sliding window of recently arrived data may be maintained, meaning that old data must be removed as time goes on. Furthermore, as the contents of the sliding windows evolve over time, it makes sense for users to ask a query once and receive updated answers over time. <br /><br /> This dissertation begins with the observation that the two fundamental requirements of a DSMS are dealing with transient (time-evolving) rather than static data and answering persistent rather than transient queries. One implication of the first requirement is that data maintenance costs have a significant effect on the performance of a DSMS. Additionally, traditional query processing algorithms must be re-engineered for the sliding window model because queries may need to re-process expired data and "undo" previously generated results. The second requirement suggests that a DSMS may execute a large number of persistent queries at the same time, therefore there exist opportunities for resource sharing among similar queries. <br /><br /> The purpose of this dissertation is to develop solutions for efficient query processing over sliding windows by focusing on these two fundamental properties. In terms of the transient nature of streaming data, this dissertation is based upon the following insight. Although the data keep changing over time as the windows slide forward, the changes are not random; on the contrary, the inputs and outputs of a DSMS exhibit patterns in the way the data are inserted and deleted. It will be shown that the knowledge of these patterns leads to an understanding of the semantics of persistent queries, lower window maintenance costs, as well as novel query processing, query optimization, and concurrency control strategies. In the context of the persistent nature of DSMS queries, the insight behind the proposed solution is that various queries may need to be refreshed at different times, therefore synchronizing the refresh schedules of similar queries creates more opportunities for resource sharing.

In this thesis we study the problem of requiring self-interested agents need to interact with some centralized mechanism where this interaction is costly. To improve their utility, agents may choose to interact with \emph{neighbours} in order to coordinate their actions, potentially resulting in savings with respect to total interaction costs for all involved. We highlight the issues that arise in such a setting for the mechanism as well as for the agents. We use a mechanism-design approach to study this problem and present a model for self-interested agents to form groups with neighbours in order to reduce the total interaction cost. Our model focuses on two aspects: reward-distribution and cost-sharing. We look at two scenarios for reward-distribution mechanisms and proposed a core-stable payoff as well as a fair payoff mechanism. We then propose a cost-sharing mechanism that agents can use to coordinate and reduce their interaction costs. We prove this mechanism to be incentive-compatible, cost-recovery and fair. We also discuss how agents might form groups in order to save on cost. We study how our final outcome (the total percentage of savings as a group) depends on the agents' interaction topology and analyze different topologies. In addition we carry out experiments which further validate our proposal.

The KioskNet project aims to provide extremely low-cost Internet access to rural kiosks in developing countries, where conventional access technologies, \eg\, DSL, CDMA and dial-up, are currently economically infeasible. In the KioskNet architecture, an Internet-based proxy gathers data from the Internet and sends it to a set of edge nodes, called ``gateways'' from which ferries, such as buses and cars, opportunistically pick up the data using short-range WiFi as they drive past, and deliver it wirelessly to kiosks in remote villages. The first part of this thesis studies the downlink scheduling problem in the context of KioskNet. We pose the following question: assuming knowledge of the bus schedules, when and to which gateway should the proxy send each data bundle so that 1) the bandwidth is shared fairly and 2) given 1), the overall delay is minimized? We show that an existing schedule-aware scheme proposed in the literature, \ie\, EDLQ~\cite{JainFP04}, while superficially appearing to perform well, has some inherent limitations which could lead to poor performance in some situations. Moreover, EDLQ does not provide means to enforce desired bandwidth allocations. To remedy these problems, we employ a token-bucket mechanism to enforce fairness and decouple fairness and delay-minimization concerns. We then describe a utility-based scheduling algorithm which repeatedly computes an optimal schedule for all eligible bundles as they come in. We formulate this optimal scheduling problem as a minimum-cost network-flow problem, for which efficient algorithms exist. Through simulations, we show that the proposed scheme performs at least as well as EDLQ in scenarios that favour EDLQ and achieves up to 40\% reduction in delay in those that do not. Simulation results also indicate that our scheme is robust against the randomness in actual timing of buses. The second part of the thesis shares some of our experience with building and testing the software for KioskNet. We subjected a prototype of the KioskNet system, built on top of the DTN reference implementation, to stress tests and were able to identify and fix several software defects which severely limited the performance. From this experience, we abstract some general principles common to software that deals with opportunistic communication.

Traditional, general-purpose operating systems strictly separate user processes from the kernel. Processes can only communicate with the kernel through system calls. As a means to ensure system security, system calls inevitably involve performance overhead. Direct User Callback from the Kernel, or DUCK, is a framework that improves the performance of network-centric applications by executing a part of application code directly from inside the kernel. Because the code runs in kernel mode and can access kernel memory directly, DUCK is able to eliminate two important sources of system call overhead, namely mode switches and data copying. One issue with DUCK is how to design an application programming interface (API) that is general, efficient, and easy to use. In this thesis, we present the design of the DUCK API, which includes functions for both direct user code execution and zero-copy buffer management. We have implemented DUCK prototypes on the Solaris/SPARC platform. An efficient way to implement direct user code invocation is through memory sharing between the kernel and user processes. However, because Solaris/SPARC separates the user and kernel address spaces, achieving memory sharing is difficult. In the thesis, we study the SPARC architecture and the Solaris virtual memory subsystem, and discuss three potential approaches to support memory sharing required by DUCK. We proceed to present micro-benchmark experiments demonstrating that our DUCK prototype implementation is capable of improving the peak throughput of a simple UDP forwarder by 28% to 44%.

Bi-clustering, i.e. simultaneously clustering the rows and columns of matrices based on their entries, covers a large variety of techniques in data mining. The goal of all bi-clustering techniques is finding the partitions of the rows and the columns in which sub-rows and sub-columns show a similar behavior. Currently existing algorithms for bi-clustering problems are either heuristic, or try to solve approximations of the original problems. There is no efficient algorithm for exact bi-clustering problems. The computational complexity of bi-clustering problems depends on the exact problem formulation, and particularly on the merit function used to evaluate the quality of a given bi-clustering partition. The computational complexity of most of the common bi-clustering problems is unknown. In this thesis, we present a formal definition for the homogeneous cover problem. This problem has many applications from bio-informatics to targeted marketing. We analyze its computational complexity and show that the problem is NP-hard.