The "String Quartet" is constructed upon the form of a theme and seven variations. It is the principal purpose of the theme to provide a unifying musical idea, and the variations to provide a continuous line of development of that idea The characteristics of simplicity and directness in the construction of the theme, not unusual in the variation form, furnish the source materials for extensive development that progresses in levels of complexity in each variation. A return to the theme, again with simplicity and directness, completes the unifying musical idea of the composition.

The first movement is probably best catalogued as highly altered sonata-allegro in form. Exposition of the main thematic material is in the form of a fugue. The main thematic germ of this entire work may be found in the first three ascending fourths.

No description available.

No description available.

No description available.

<p> A string is a sequence of various simple elements. The most straightforward examples of strings are English words-concatenations of the 26 letters of the English alphabet. A repetition in a string x is a nonempty substring of the form x[i..j] = u^k, k ≥ 2. The study of repetitions in strings is as old as the study of strings themselves. Furthermore, the identification of repetitions in a given finite string still remains an important topic in a variety of contexts: pattern-matching, computational biology, data compression, cryptology, and many other areas. </p> <p> A run in a string xis a substring in the form x[i..j] = u^kv, k ≥ 2 where v is a prefix of u, u is not a repetition itself, and this substring x[i..j] is neither left-extendible nor right-extendible. The notion of runs thus captures the notion of leftmost maximal repetitions and allows for a succinct notation [M89]. The maximal number of runs over all strings of length n is denoted as p(n). To determine the properties of the function p(n) is an important aspect of the research in periodicities in strings. </p> <p> Prior to the asymptotic lower bound presented by Franek and myself in [FY06] (presented here in Chapter 2), there had been no known non-trivial lower bound for p(n), asymptotic or otherwise. A result suggesting a possible lower bound was presented by Franek, Simpson and Smyth in 2003, introducing a construction of a sequence of strings {xn}~=0, so that limn→∞ r(Xn)/[Xn] = 3/(1+√5) ≈ 0.927 [FSS03]. Theirmethod was extended to provide a true asymptotic lower bound in [FY06]. In the first part of Chapter 2, the recursive construction of the sequence of strings from [FSS03] is presented with all details not discussed in either [FSS03] or [FY06]. In the second part of Chapter 2, a construction of the lower bound is presented with all details. This part represents my original contribution to the research. </p> <p> I designed a new approach to generate strings that are "rich in runs" other then the one used in [FSS03] and [FY06]. A similar approach as in Chapter 2 is used to construct a lower bound for p(n) using the alternate construction of sequences of strings. This new construction method gives, interestingly, sequences with the same limit as in [FY06], thus giving some support to the conjecture that limn→∞ p(n)/n = 3/(1+√5) stated in [FSS03]. This method is presented in Chapter 3. The whole Chapter 3 thus represents another part of my original contribution to the research. </p> <p> It had been known since the 1980's that the number of repetitions in a string of length n is at most of the order O(n log n). A remarkable result by Kolpakov and Kucherov in 2000 showed that p(n) was in fact bounded by a function linear in n [KK00]. Their approach only. provided the existence of such a function, not the concrete values of its constants. Recently, Rytter improved the upper bound of p(n) to 5n. [R06). The paper by Rytter was published in a conference proceedings and as such lacked many details in some areas and was bit too vague. In Chapter 4 I present Rytter's proof with all relevant details filled in. Through a private communication I learned at the time of writing of this thesis that the upper bound had been improved by Rytter, and independently by Smyth, Simpson, and Puglisi to 3.5n. The latest upper bound is supposed to be now as low as 1.5n. However, none of the upper bounds better than 5n has been published yet. </p> <p> In the last chapter I discuss my conclusions and point out the directions for the future research. </p> / Thesis / Master of Science (MSc)

A string is a sequence of symbols, usually called letters, drawn from some alphabet. It is one of the most fundamental and important structures in computing, bioinformatics and mathematics. Computer files, contents of a computer memory, network and satellite signals are all instances of strings. The genome of every living thing can be represented by a string drawn from the alphabet {a, c, g, t}. The algorithms processing strings have a wide range of applications such as information retrieval, search engines, data compression, cryptography and bioinformatics. In a DNA sequence the indeterminate symbol {a, c} is used when it is unclear whether a given nucleotide is a or c, We could then say that {a, c} matches another symbol {c, g} which in turn matches {g, t}, but {a, c} certainly does not match {g, t}. The processing of indeterminate strings is much more difficult because of this nontransitivity of matching. Thus a combinatorial understanding of indeterminate strings becomes essential to the development of efficient methods for their processing. With indeterminate strings, as with ordinary ones, the main task is the recognition/computation of patterns called regularities . We are particularly interested in regularities called repeats, whether tandem such as acgacg or nontandem (acgtacg). In this thesis we focus on newly-discovered regularities in strings, especially the enhanced cover array and the Lyndon array, with attention paid to extending the computations to indeterminate strings. Much of this work is necessarily abstract in nature, because the intention is to produce results that are applicable over a wide range of application areas. We will focus on finding algorithms to construct different data structures to represent strings such as cover arrays and Lyndon arrays. The idea of cover comes from strings which are not truly periodic but "almost" periodic in nature. For example abaababa is covered by aba but is not periodic. Similarly the Lyndon array describes the string in another unique way and is used in many fields of string algorithms. These data structures will help us in the field of string processing. As one application of these data structures we will work on "Reverse Engineering"; that is, given data structures derived from of a string, how can we get the string back. Since DNA, RNA and peptide sequences are effectively "strings" with unique properties, we will adapt our algorithms for regular or indeterminate strings to these sequences. Sequence analysis can be used to assign function to genes and proteins by observing the similarities between the compared sequences. Identifying unusual repetitive patterns will aid in the identification of intrinsic features of the sequence such as active sites, gene-structures and regulatory elements. As an application of periodic strings we investigate microsatellites which are short repetitive DNA patterns where repeated substrings are of length 2 to 5. Microsatellites are used in a wide range of studies due to their small size and repetitive nature, and they have played an important role in the identification of numerous important genetic loci. A deeper understanding of the evolutionary and mutational properties of microsatellites is needed, not only to understand how the genome is organized, but also to correctly interpret and use microsatellite data in population genetics studies. / Thesis / Doctor of Philosophy (PhD)

The six-movement work is scored for two violins, a viola, and a violoncello. A new approach toward the decision making of the compositional process is revealed which structures the parameters of the composition along an arbitrary frame of reference. This reference is selected prior to composition and influences every aspect of the work. The reference chosen is an existing musical work used in quotation and for stylistic modeling, paraphrase, and variation. Consonance, dissonance, and thematic development are defined in terms of this source.

Sinfonia is a two movement work for chamber string orchestra and percussion consisting of at least five violins I, five violins II, five violas, five cellos, three string basses, and three percussionists playing timpani, two suspended cymbals, one small crash cymbal, 2 triangles, tambourine, woodblock, five temple blocks, snare, two tom-toms, 2 glockenspiels, xylophone, and chimes. The first movement is approximately nine minutes long, the second lasts five and one third minutes making a total of approximately fourteen minutes and twenty seconds.

The StringToStringCorrection problem asks, given mutable string M, target string T, and positive integer k, can M be mutated into T using at most k operations (single symbol deletions or swaps of adjacent symbols) applied to M? The problem is known to be NP-complete. Abu-Khzam et al. give the first fixed-parameter algorithm for the problem when the parameter is the number of operations permitted. Their technique, charge and reduce, gives a O^∗(1.612k) bounded search tree algorithm, but leaves open whether a poly-size kernel exists. We show, using two polynomial time reduction rules on large regions of the input strings, that the problem has a problem kernel of size O(k^4). Our algorithm achieves this in a polynomial running time. Additionally, we introduce the problem k-MultiStringToStringCorrection (k-MS2SC), a generalized version of StringToStringCorrection, and prove it to be fixed-parameter tractable. / Graduate / 0984 / nwatt@uvic.ca