bluuebunny/crossref_metadata_2025 huggingface dataset:
A new source for the polyphonic conductus: MS 117 in Sidney Sussex College, Cambridge
Authors: Everist Mark
Published: September 2008

The extent to which the surviving sources can demonstrate the cultivation and consumption of the music of the twelfth and thirteenth centuries differs for each of the genres represented in them. Thus although the versions of the so-calledMagnus liber organicontained in the three principal ‘Notre-Dame’ sources are sufficiently different to suggest that in a critical edition they should be edited separately, they are similar enough to allow us to infer a certain amount about the origins and cultivation of the music.
Busnois' motet In hydrauliscise in textual reconstruction and analysis
Authors: Howlett David
Published: September 2008

Munich, Bayerische Staatsbibliothek, Mus. MS 3154 folios 47v–48r preserves the unique text of Busnois' motetIn hydraulis, reproduced by D. Plamenac inDie Musik in Geschichte und GegenwartIX Tafel 116.
Marian texts and themes in an English manuscript: a miscellany in two parts
Authors: Page Christopher
Published: September 2008

Michael Morrow was an acute reader of medieval literature, and one who knew that every medieval text is a potential source of information for the modern performer and musicologist. A striking example is provided by the 453 chapters of a fifteenth-century anthology now in the library of Sidney Sussex College, Cambridge. This imposing book appears to be one of the largest collections of Marian miracle-stories in the world. Assembled in the year 1409, perhaps in East Anglia, it contains forty-nine chapters about Marian devotions, liturgies, plainsongs and prayers, among them several texts that were set by English composers:Salve regina(there are ten chapters devoted to this chant alone),Alma redemptoris mater, Gaude flore virginali, Sancta Maria non est tibi similis, Salve sancta parens, Gaude Maria virgo, Ave maris StellaandGaude virgo mater Christi.
Josquin and Milan
Authors: Fallows David
Published: September 2008

Writing in 1882, Edmond Vander Straeten was the first to argue that the name ‘Juschino’ among the singers of Galeazzo Maria Sforza's household chapel referred to the composer Josquin des Prez. Assuming a birthdate in the early 1450s, Vander Straeten found it easy to understand why the young Josquin was at the bottom of the salary scale in 1475, the date of the documents. Soon afterwards, Eugenio Motta provided new evidence to support that identification and stretch Josquin's Milanese career to 1479. Since then the years in Milan have had a fixed and central place in all studies of Josquin's life.
A Jerusalem chant for the Holy Cross in the Byzantine, Latin and Eastern Rites
Authors: Dubowchik Rosemary Thoonen
Published: September 2008

In the year 552, a ceremony was held to commemorate the first anniversary of the death of Martha, mother of St Simeon Stylites the Younger. The Vita of St Martha, written by an anonymous monk during the first half of the seventh century, records that the priest Antonio journeyed from Simeon's pillar at Mount Admirabilis, near Antioch, to Jerusalem to obtain a fragment of the cross. When Antonio returned to Mount Admirabilis, ‘a great crowd of men and women gathered in the grace of God, with candles and torches, to hold the service in her memory: and having kept a vigil all night, when in the early morning the living cross was displayed, all who were gathered worshipped, crying out with hymns: We adore your cross, Lord, and we glorify your holy resurrection.’
Elaboration through exhortation: troping Motets for the Common of Martyrs
Authors: Kidwell Susan A.
Published: September 2008

It is common knowledge that the repertory of thirteenth-century Latin motets exhibits a great variety of poetic themes. Many of the earliest motets comment upon the feast of their parent chant and are therefore classified as ‘troping’; others praise the Virgin Mary – sometimes regardless of their associated chant; still others avoid obvious connections with the liturgy and either criticize, admonish or exhort listeners to reform. The classification of motet texts according to content has increased our understanding of overall themes and of the chronological relationships between them, but it has also raised questions. Some questions arise from the fact that the general categories of troping, Marian and hortatory texts are not mutually exclusive. Should we distinguish a ‘general’ Marian motet, like Virgo mater salutis (386) / JOHANNE (M 29), which superimposes general epithets and intercessions to the Virgin above a chant in honour of John the Baptist, from a ‘troping’ Marian motet, such as Flos de spina rumpitur (437), built over the Assumption tenor, REGNAT (M 34), which makes specific references to its associated feast? Or does this added taxonomic layer only distract us from the task of interpreting these texts?
Tinctoris on the great composers
Authors: Holford-Strevens Leofranc
Published: September 2008

Johannes Tinctoris, in the prologue to his Liber de arte contrapuncti of 1477, having demonstrated his wide literary and philosophical culture, and declared that, to his astonishment, no music over forty years old is deemed worthy by the learned of a hearing, praises five living composers and three recently deceased, whose works are of such sweet savour that he judges them worthy even of the immortal gods; in so elegant a context only the pagan phrase will serve. He continues (§18): ‘Ea quoque profecto numquam audio, numquam considero quin laetior ac doctior evadam, unde quemadmodum Virgilius in illo opere divino Eneidos Homero, ita iis hercule in meis opusculis utor archetypis’.
Contenance angloise andaccidentals in some motets by Du Fay
Authors: Brothers Thomas
Published: September 2008

Again and again, one discovers two patterns of movement yielding innovations in the history of European music: regional styles that were previously distinct from one another merge together in synthesis, as do stylistic tendencies that were previously tied to different genres. Both patterns may be invoked in an attempt to historicize the use of accidentals in a handful of important motets by Guillaume Du Fay, includingNuper rosarum floresand the tropedAve regina celorum. Historians have hardly been unaware of the importance of the influence of English music on Du Fay, nor have they been unaware of Du Fay's interest in transferring stylistic features from one genre to another. But it is useful to bring these two perspectives together, especially given the advance of recent scholarship. Our analysis may proceed from the basis of two well-known statements from the period. The first, from a treatise (c. 1400) attributed to the composer Philipoctus de Caserta, states that:
Tonal neumes in Anglo-Saxon and Anglo-Norman pontificals
Authors: Kozachek Thomas
Published: September 2008

The earliest efforts to represent accurately the intervallic structure of a melody, beyond the general shape encoded in non-diastematic neumes, or to indicate specific degrees in the gamut, are commonly associated with musical notations of the latter part of the eleventh century. In various chant manuscripts of this period we find systematic use of common or special note shapes, strictly diastematic writing with respect to a drypoint line, and the earliest surviving staff notations.
The medieval Russian Kondakar and the choirbook from Kastoria: a palaeographic study in Byzantine and Slavic musical relations
Authors: Myers Gregory
Published: September 2008

The Byzantine choirbook or Asmatikon was a musical anthology of melismatic chants for the Office and Liturgy of the fixed and movable parts of the Church year. With its counterpart for the soloist, the Psaltikon, the Asmatikon flourished in the twelfth and thirteenth centuries and was then superseded in the fourteenth and fifteenth by a new manuscript type known as the Akolouthia, which absorbed much of the material from the older sources and added collections of new chants. The older manuscript types were distinguished not only by their repertory of chants, but by separate modal and melodic traditions and stock of characteristic melodic formulae.1
Teachers, booksellers and taxes: reinvestigating the life and activities of Johannes de Garlandia
Authors: Whitcomb Pamela
Published: September 2008

Johannes de Garlandia is one of the most important theorists of measurable music during the thirteenth century, yet the study of his writings has always been frustrated by a problematic biographical situation. Not only is the history of manuscript transmission and attribution regarding Johannes de Garlandia's writings complicated, but both Johannes and de Garlandia were popular and common names in medieval Paris, where the theorist is thought to have lived.
The vision of music in a Lollard florilegium: Cantus in the Middle English Rosarium theologie (Cambridge, Gonville and Caius College MS 354/581)
Authors: Holsinger Bruce W.
Published: September 2008

Despite their intriguing testimony to the vagaries of musical life in late medieval England, relatively little attention has been given by musicologists and historians of religion to the wealth of commentary on liturgical and secular music penned by the followers of the Oxford heretic John Wyclif. In a brief mention of this material in The Premature Reformation, her magisterial study of Wyclif and the Lollards, Anne Hudson suggests that the Lollards’ suspicion of musical display reflected their more general hostility towards the decoration of churches.
Maximum Waiting Times are Asymptotically Independent
Authors: Móri Tamás F.
Published: September 2008

For every n consider a subset Hn of the patterns of length n over a fixed finite alphabet. The limit distribution of the waiting time until each element of Hn appears in an infinite sequence of independent, uniformly distributed random letters was determined in an earlier paper. This time we prove that these waiting times are getting independent as n → ∞. Our result is used for applying the converse part of the Borel–Cantelli lemma to problems connected with such waiting times, yielding thus improvements on some known theorems.
Duality in Polymatroids and Set Functions
Authors: Whittle Geoff
Published: September 2008

Notions of deletion and contraction for the class of set functions from finite sets into the integers are defined. An operation on a subclass of such set functions is a function from the subclass into itself that preserves ground sets and respects isomorphism. The operations on set functions that interchange deletion and contraction are characterised, as are those with the further property of being involutary. Similar results are given for polymatroids. There is a unique involutary operation on the class of k-polymatroids that interchanges deletion and contraction. The results generalise those of Kung [3].
Greedy Search on the Binary Tree with Random Edge-Weights
Authors: Aldous David
Published: September 2008

There is a simple greedy algorithm for seeking large values of a function f defined on the vertices of the binary tree. Modeling f as a random function whose increments along edges are i.i.d., we show that (under a natural assumption) the values found by the greedy algorithm grow linearly in time, with rate specified in terms of a fixed-point identity for distributions.
Optimal Strategy for the First Player in the Penney Ante Game
Authors: Csirik János A.
Published: September 2008

In the Penney Ante game two players choose one binary string of length k each in turn, and toss a coin repeatedly. If at some stage the last k outcomes match one of their strings, the player with that string wins. The case k ≤ 4 is somewhat exceptional and in any case easily done. For k ≥ 5, Guibas and Odlyzko proved that the second player's optimal strategy is to choose the first k − 1 digits of the first player's string prefixed by 0 or 1. They conjectured that these two choices are never equally good. We prove that this conjecture is correct. Then we prove that 01…100 (with k − 1 ones) is an optimal strategy for the first player, and find all the strategies that are equally good.
Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
Authors: Sinclair Alistair
Published: September 2008

The paper is concerned with tools for the quantitative analysis of finite Markov chains whose states are combinatorial structures. Chains of this kind have algorithmic applications in many areas, including random sampling, approximate counting, statistical physics and combinatorial optimisation. The efficiency of the resulting algorithms depends crucially on the mixing rate of the chain,i.e., the time taken for it to reach its stationary or equilibrium distribution.

The paper presents a new upper bound on the mixing rate, based on the solution to a multicommodity flow problem in the Markov chain viewed as a graph. The bound gives sharper estimates for the mixing rate of several important complex Markov chains. As a result, improved bounds are obtained for the runtimes of randomised approximation algorithms for various problems, including computing the permanent of a 0–1 matrix, counting matchings in graphs, and computing the partition function of a ferromagnetic Ising system. Moreover, solutions to the multicommodity flow problem are shown to capture the mixing rate quite closely: thus, under fairly general conditions, a Markov chain is rapidly mixing if and only if it supports a flow of low cost.
A Theorem on Reconstruction of Random Graphs
Authors: Cameron Peter J. , Martins Cleide
Published: September 2008

In this paper we prove that given a finite collection of finite graphs, and the subsets of vertices of a random graph G that induce those graphs, it is almost always possible to uniquely reconstruct a class of graphs equivalent to G.
Hamilton Cycles in Oriented Graphs
Authors: Häggkvist Roland
Published: September 2008

It is shown that an oriented graph of order n whose every indegree and outdegree is at least cn is hamiltonian if c ≥ ½ − 2−15 but need not be if c < ⅜.
Random Matrices and Brownian Motion
Authors: Goh William M. Y. , Schmutz Eric
Published: September 2008

For T ∈ GLn (Fq), let Ωn (t, T) be the number of irreducible factors of degree less than or equal to nt in the characteristic polynomial of T. Let

and suppose T is chosen from G Ln(Fq) at random uniformly. We prove that the stochastic process ≺Zn(t)≻t∈[0, 1] converges to the standard Brownian motion process W(t), as n → ∞.
A Discrete Analogue of a Theorem of Makarov
Authors: Lawler Gregory F.
Published: September 2008

A theorem of Makarov states that the harmonic measure of a connected subset of ℝ2 is supported on a set of Hausdorff dimension one. This paper gives an analogue of this theorem for discrete harmonic measure, i.e., the hitting measure of simple random walk. It is proved that for any 1/2 < α < 1, β < α − 1/2, there is a constant k such that for any connected subset A ⊂ ℤ2 of radius n,

where HA denotes discrete harmonic measure.
Random Permutations: Some Group-Theoretic Aspects
Authors: Cameron Peter J. , Kantor William M.
Published: September 2008

The study of asymptotics of random permutations was initiated by Erdős and Turáan, in a series of papers from 1965 to 1968, and has been much studied since. Recent developments in permutation group theory make it reasonable to ask questions with a more group-theoretic flavour. Two examples considered here are membership in a proper transitive subgroup, and the intersection of a subgroup with a random conjugate. These both arise from other topics (quasigroups, bases for permutation groups, and design constructions).
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
Authors: Dyer Martin , Frieze Alan , Kannan Ravi , Kapoor Ajai , Perkovic Ljubomir , Vazirani Umesh
Published: September 2008

We describe a time randomized algorithm that estimates the number of feasible solutions of a multidimensional knapsack problem within 1 ± ε of the exact number. (Here r is the number of constraints and n is the number of integer variables.) The algorithm uses a Markov chain to generate an almost uniform random solution to the problem.
A Random Recolouring Method for Graphs and Hypergraphs
Authors: McDiarmid Colin
Published: September 2008

We consider a simple randomised algorithm that seeks a weak 2-colouring of a hypergraph H; that is, it tries to 2-colour the points of H so that no edge is monochromatic. If H has a particular well-behaved form of such a colouring, then the method is successful within expected number of iterations O(n3) when H has n points. In particular, when applied to a graph G with n nodes and chromatic number 3, the method yields a 2-colouring of the vertices such that no triangle is monochromatic in expected time O(n4).
Some Local Extremal Connectivity Results for Matroids
Authors: Akkari Safwan , Oxley James
Published: September 2008

Tutte proved that if e is an element of a 3-connected matroid M such that neither M\e nor M/e is 3-connected, then e is in a 3-circuit or a 3-cocircuit. In this paper, we prove a broad generalization of this result. Among the consequences of this generalization are that if X is an (n − 1)-element subset of an n-connected matroid M such that neither M\X nor M/X is connected, then, provided |E(M)| ≥ 2(n − 1)≥ 4, X is in both an n-element circuit and an n-element cocircuit. When n = 3, we describe the structure of M more closely using Δ − Y exchanges. Several related results are proved and we also show that, for all fields F other than GF(2), the set of excluded minors for F-representability is closed under both Δ − Y and Y − Δ exchanges.
Nearly Equal Distances in the Plane
Authors: Erdős Paul , Makai Endre , Pach János
Published: September 2008

For any positive integer k and ε > 0, there exist nk,ε, ck, e > 0 with the following property. Given any system of n > nk,ε points in the plane with minimal distance at least 1 and any t1, t2…, tk ≥ 1, the number of those pairs of points whose distance is between ti and for some 1 ≤ i ≤ k, is at most (n2/2) (1 − 1/(k+1)+ε). This bound is asymptotically tight.
Clique Partitions of Chordal Graphs
Authors: Erdős Paul , Ordman Edward T. , Zalcstein Yechezkel
Published: September 2008

To partition the edges of a chordal graph on n vertices into cliques may require as many as n2/6 cliques; there is an example requiring this many, which is also a threshold graph and a split graph. It is unknown whether this many cliques will always suffice. We are able to show that (1 − c)n2/4 cliques will suffice for some c > 0.
On Random Generation of the Symmetric Group
Authors: Łuczak Tomasz , Pyber László
Published: September 2008

We prove that the probability i(n, k) that a random permutation of an n element set has an invariant subset of precisely k elements decreases as a power of k, for k ≤ n/2. Using this fact, we prove that the fraction of elements of Sn belong to transitive subgroups other than Sn or An tends to 0 when n → ∞, as conjectured by Cameron. Finally, we show that for every ∈ > 0 there exists a constant C such that C elements of the symmetric group Sn, chosen randomly and independently, generate invariably Sn with probability at least 1 − ∈. This confirms a conjecture of McKay.
Constructing Small Sets that are Uniform in Arithmetic Progressions
Authors: Razborov A. , Szemerédi E. , Wigderson A.
Published: September 2008

For every integer N, we explicitly construct a subset of residues mod N of size(log N)o(1) which is nearly uniformly distributed in every arithmetic progression modulo N.
Recognizing Polymatroids Associated with Hypergraphs
Authors: Vertigan Dirk , Whittle Geoff
Published: September 2008

Two natural classes of polymatroids can be associated with hypergraphs: the so-called Boolean and hypergraphic polymatroids. Boolean polymatroids carry virtually all the structure of hypergraphs; hypergraphic polymatroids generalize graphic matroids. This paper considers algorithmic problems associated with recognizing members of these classes. Let k be a fixed positive integer and assume that the k-polymatroid ρ is presented via a rank oracle. We present an algorithm that determines in polynomial time whether ρ is Boolean, and if it is, finds the hypergraph. We also give an algorithm that decides in polynomial time whether ρ is the hypergraphic polymatroid associated with a given hypergraph. Other structure-theoretic results are also given.
Hamilton Cycles in Random Regular Digraphs
Authors: Cooper Colin , Frieze Alan , Molloy Michael
Published: September 2008

We prove that almost every r-regular digraph is Hamiltonian for all fixed r ≥ 3.
The Growth of Infinite Graphs: Boundedness and Finite Spreading
Authors: Diestel Reinhard , Leader Imre
Published: September 2008

An infinite graph is called bounded if for every labelling of its vertices with natural numbers there exists a sequence of natural numbers which eventually exceeds the labelling along any ray in the graph. Thomassen has conjectured that a countable graph is bounded if and only if its edges can be oriented, possibly both ways, so that every vertex has finite out-degree and every ray has a forward oriented tail. We present a counterexample to this conjecture.
The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
Authors: Janson Svante
Published: September 2008

The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph Gnm are shown to be asymptotically normal if m is neither too large nor too small. At the lowest limit m ≍ n3/2, these numbers are asymptotically log-normal. For Gnp, the numbers are asymptotically log-normal for a wide range of p, including p constant. The same results are obtained for random directed graphs and bipartite graphs. The results are proved using decomposition and projection methods.
Amalgamated Factorizations of Complete Graphs
Authors: Dugdale J. K. , Hilton A. J. W.
Published: September 2008

We give some sufficient conditions for an (S, U)-outline T-factorization of Kn to be an (S, U)-amalgamated T-factorization of Kn. We then apply these to give various necessary and sufficient conditions for edge coloured graphs G to have recoverable embeddings in T-factorized Kn's.
Topological Cliques in Graphs
Authors: komlós János , Szemerédi Endre
Published: September 2008

Let f(t) be the largest integer such that every graph with average degree t has a topological clique with f(i) vertices. It is widely believed that . Here we prove the weaker estimate .
On Vertex-Edge-Critically n-Connected Graphs
Authors: Mader W.
Published: September 2008

All digraphs are determined that have the property that when any vertex and any edge that are not adjacent are deleted, the connectivity number decreases by two.
On Partitioning and Packing Products with Rectangles
Authors: Ahlswede Rudolf , Cai Ning
Published: September 2008

In [1] we introduced and studied for product hypergraphs where ℋi = (i,ℰi), the minimal size π(ℋn) of a partition of into sets that are elements of . The main result was that

if the ℋis are graphs with all loops included. A key step in the proof concerns the special case of complete graphs. Here we show that (1) also holds when the ℋi are complete d-uniform hypergraphs with all loops included, subject to a condition on the sizes of the i. We also present an upper bound on packing numbers.
Properties of Large Eden Clusters in the Plane
Authors: Hammersley J. M. , Mazzarino G.
Published: September 2008

Whereas the cylindrical version of an Eden cluster in the plane has a surface roughness with a fractal dimension predicted by theory, the central version has hitherto seemed to conflict with theory. However, a fresh way of analysing computer simulations of the central version shows that this anomaly is more apparent than real, and the central version can thereby be reconciled with theory. As a by-product, we obtain statistical data on the properties of the central version in the plane. The macroscopic shape of a central cluster is not circular, and microscopic roughness depends weakly upon the angular direction of portions of the surface. Rather surprisingly, the edge method of construction gives a more nearly circular shape than the external and internal methods. For higher dimensions than the plane, the corresponding treatment is more difficult, and there the situation remains obscure. Higher dimensions and certain other clusters (e.g.Richardson clusters) are treated briefly in Section 6. The theory of surface roughness uses a spatial generalization of martingales, called a serial harness: this is also described in Section 6.
Block Reduced Lattice Bases and Successive Minima
Authors: Schnorr C. P.
Published: September 2008

A lattice basis bi,…,bm is called block reduced with block size β if for every β consecutive vectors bi,…,bi+β−1, the orthogonal projections of bi,…,bi+β−1 in span(bi,…,bi−1)⊥ are reduced in the sense of Hermite and Korkin–Zolotarev. Let λi denote the successive minima of lattice L, and let b1,…,bm be a basis of L that is block reduced with block size β. We prove that for i = 1,…, m

where γβ is the Hermite constant for dimension β. For block size β = 3 and odd rank m ≥ 3, we show that

where the maximum is taken over all block reduced bases of all lattices L. We present critical block reduced bases achieving this maximum. Using block reduced bases, we improve Babai's construction of a nearby lattice point. Given a block reduced basis with block size β of the lattice L, and given a point x in the span of L, a lattice point υ can be found in time βO(β) satisfying

These results also give improvements on the method of solving integer programming problems via basis reduction.
Graph Minors I: A Short Proof of the Path-width Theorem
Authors: Diestel Reinhard
Published: September 2008

Robertson and Seymour proved that excluding any fixed forest F as a minorimposes a bound on the path-width of a graph. We give a short proof of this, reobtaining the best possible bound of |F| – 2.
On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
Authors: Verbitsky Oleg
Published: September 2008

We focus our attention on the class RMAX(2) of NP optimization problems. Owing to recent developments in interactive proof techniques, RMAX(2) was shown to be the lowest class of logical classification that contains problems hard to approximate. Namely, the RMAX(2)-complete problem MAX CLIQUE (of finding the size of the largest clique in a graph) is not approximable in polynomial time within any constant factor unless NP=P.

We are interested in problems inside RMAX(2) that are not known to be complete but are still hard to approximate. We point out that one such problem is MAXlog n, n, considered by Berman and Schnitger: given m conjunctions, each of them consisting of log m propositional variables or their negations, find the maximal number of simultaneously satisfiable conjunctions. We also obtain the approximation hardness results for some other problems in RMAX(2). Finally, we discuss the question of whether or not the problems under consideration are RMAX(2)-complete.
Substitution Method Critical Probability Bounds for the Square Lattice Site Percolation Model
Authors: Wierman John C.
Published: September 2008

The square lattice site percolation model critical probability is shown to be at most .679492, improving the best previous mathematically rigorous upper bound. This bound is derived by extending the substitution method to apply to site percolation models.
The Induced Size-Ramsey Number of Cycles
Authors: Haxell P. E. , Kohayakawa Y. , Łuczak T.
Published: September 2008

For a graph H and an integer r ≥ 2, the induced r-size-Ramsey number of H is defined to be the smallest integer m for which there exists a graph G with m edges with the following property: however one colours the edges of G with r colours, there always exists a monochromatic induced subgraph H′ of G that is isomorphic to H. This is a concept closely related to the classical r-size-Ramsey number of Erdős, Faudree, Rousseau and Schelp, and to the r-induced Ramsey number, a natural notion that appears in problems and conjectures due to, among others, Graham and Rödl, and Trotter. Here, we prove a result that implies that the induced r-size-Ramsey number of the cycle Cℓ is at most crℓ for some constant cr that depends only upon r. Thus we settle a conjecture of Graham and Rödl, which states that the above holds for the path Pℓ of order ℓ and also generalise in part a result of Bollobás, Burr and Reimer that implies that the r-size Ramsey number of the cycle Cℓ is linear in ℓ Our method of proof is heavily based on techniques from the theory of random graphs and on a variant of the powerful regularity lemma of Szemerédi.
First Occurrence in Pairs of Long Words: A Penney-ante Conjecture of Pevzner
Authors: Stark Dudley
Published: September 2008

Suppose X1, X2,… is a sequence of independent and identically distributed random elements whose values are taken in a finite set S of size |S| ≥ 2 with probability distribution ℙ(X = s) = p(s) > 0 for s ∈ S. Pevzner has conjectured that for every probability distribution ℙ there exists an N > 0 such that for every word A with letters in S whose length is at least N, there exists a second word B of the same length as A, such that the event that B appears before A in the sequence X1, X2,… has greater probability than that of A appearing before B. In this paper it is shown that a distribution ℙ satisfies Pevzner's conclusion if and only if the maximum value of ℙ, p, and the secondary maximum c satisfy the inequality . For |S| = 2 or |S| = 3, the inequality is true and the conjecture holds. If , then the conjecture is true when A is not allowed to consist of pure repetitions of that unique element for which the distribution takes on its mode.
Conditional Independences among Four Random Variables II
Authors: Matúš F.
Published: September 2008

Numerous new properties of stochastic conditional independence are introduced. They are aimed, together with two surprisingly trivial examples, at a further reduction of the problem of probabilistic representability for four-element sets, i.e. of the problem which conditional independences within a system of four random variables can occur simultaneously. Proofs are based on fundamental properties of conditional independence and, in the discrete case, on the use ofI-divergence and algebraic manipulations with marginal probabilities. A duality question is answered in the negative.
t-Covering Arrays: Upper Bounds and Poisson Approximations
Authors: Godbole Anant P. , Skipper Daphne E. , Sunley Rachel A.
Published: September 2008

Ak×narray with entries from theq-letter alphabet {0, 1, …,q− 1} is said to bet-coveringif eachk × tsubmatrix has (at least one set of)qtdistinct rows. We use the Lovász local lemma to obtain a general upper bound on the minimal numberK=K(n, t, q) of rows for which at-covering array exists; fort= 3 andq= 2, we are able to match the best-known such bound. LetKλ=Kλ(n, t, q), (λ ≥ 2), denote the minimum number of rows that guarantees the existence of an array for which each set oftcolumns contains, amongst its rows, each of theqtpossible ‘words’ of lengtht at least λ times. The Lovász lemma yields an upper bound onKλthat reveals how substantially fewer rows are needed to accomplish subsequentt-coverings (beyond the first). Finally, given arandom k × narray, the Stein–Chen method is employed to obtain a Poisson approximation for the number of sets oftcolumns that are deficient, i.e. missing at least one word.
Valid Generalisation from Approximate Interpolation
Authors: Anthony Martin , Bartlett Peter , Ishai Yuval , Shawe-Taylor John
Published: September 2008

Let and be sets of functions from domain X to ℝ. We say that validly generalises from approximate interpolation if and only if for each η > 0 and ∈, δ ∈ (0,1) there is m0(η, ∈, δ) such that for any function t ∈ and any probability distribution on X, if m > m0 then with m-probability at least 1 – δ, a sample X = (x1, X2,…,xm) ∈ Xm satisfies

We find conditions that are necessary and sufficient for to validly generalise from approximate interpolation, and we obtain bounds on the sample length m0{η,∈,δ) in terms of various parameters describing the expressive power of .
Asymptotic Enumeration of Predicate-Junction Flowgraphs
Authors: Cooper C.
Published: September 2008

We consider unlabelled flowgraphs for a model of binary logic without the constraints of structured programming. The number of such flowgraphs is asymptotic to (3.4n)n/2, wherenis the number of nodes in the flowgraph. This is to be compared with bounds of between (8.8)n/2and of (9.8)n/2for unlabelled structured flowgraphs of the Böhm and Jacopini type. Of the space of flowgraphs we study, 41% are prime, that is contain no proper sub-flowgraphs. The main obstructions to primality being the Dijkstra-structures, which are based onIf_Then_ElseandDo_Whileconstructs.
Orthogonality of Measures Induced by Random Walks with Scenery
Authors: Howard C. Douglas
Published: September 2008

Thinking of a deterministic function s: ℤ → ℕ as ‘scenery’ on the integers, a simple random walk on ℤ generates a random record of scenery ‘observed’ along the walk. We address this question: If t:ℤ → ℕ is another scenery on the integers and we are handed a random scenery record obtained from either s or t, under what circumstances can the source be distinguished? We allow ourselves to use information about s and t together with information contained in the scenery record. It has been conjectured that it is sufficient for t to be neither a translate of s nor a translate of the reflection of s. We show that this condition is sufficient to ensure distinguishability if s−1(δ) is finite and non-empty for some δ ∈ℕ.
Predecessors in Random Mappings
Authors: Baron Gerd , Drmota Michael , Mutafchiev Ljuben
Published: September 2008

Let ℱnbe the set of random mappings ϕ : {1,…,n} → {1,…,n} (such that every mapping is equally likely). Forxε {l,…,n} the elementsare called the predecessors ofx. LetNrdenote the random variable which counts the number of pointsxε {l,…,n} with exactlyrpredecessors. In this paper we identify the limiting distribution ofNrasn→ ∞. Ifr=r(n)=o(n⅔) then the limiting distribution is Gaussian, if r ˜Cn⅔ then it is Poisson, and in the remaining casern−⅔→ ∞ it is degenerate. Furthermore, it is shown thatNris a Poisson approximation ifr→ ∞.
Reliable Broadcasting in Hypercubes with Random Link and Node Failures
Authors: Chlebus Bogdan S. , Diks Krzysztof , Pelc Andrzej
Published: September 2008

We consider the problem of broadcasting in ann–node hypercube whose links and nodes fail independently with given probabilities p < 1 and q < 1, respectively. Information held in a fault-free node, called thesource, has to reach all other fault-free nodes. Messages may be directly transmitted to adjacent nodes only, and every node may communicate with at most one neighbour in a unit of time. A message can be transmitted only if both communicating neighbours and the link joining them are fault-free. For parameterspandqsatisfying (1 –p)(1 –q) ≽ 0.99 (e.g.p=q= 0.5%), we give an algorithm working in timeO(logn) and broadcasting source information to all fault-free nodes with probability exceeding 1 –cn-efor some positive constantε, cdepending onpandqbut not depending onn.
An Efficient Method of Examining all Trees
Authors: Kubicka Ewa
Published: September 2008

In this paper, we present a techique for examining all trees of a given order. Our approach is based on the Beyer and Hedetniemi algorithm for generating all rooted trees of a given order and on the Wright, Richmond, Odlyzko and McKay algorithm for generating all free trees of a given order. In the introduction we describe these algorithms. We also give a precise evaluation of the average number of moves it takes to generate a rooted tree, which improves the upper bound given by Beyer and Hedetniemi. In the second section we present a new method of examining all trees which uses these generating algorithms. The last section contains two applications of the method introduced. The main result of the paper is that the average number of steps required by the proposed algorithm to examine a rooted tree is bounded by a constant independent of the order of a tree.
Smallest Sets of Longest Paths with Empty Intersection
Authors: Skupień Z.
Published: September 2008

It is shown that, for every integer v < 7, there is a connected graph in which some v longest paths have empty intersection, but any v – 1 longest paths have a vertex in common. Moreover, connected graphs having seven or five minimal sets of longest paths (longest cycles) with empty intersection are presented. A 26-vertex 2-connected graph whose longest paths have empty intersection is exhibited.
Poisson mixtures
Authors: Church Kenneth W. , Gale William A.
Published: September 2008

Shannon (1948) showed that a wide range of practical problems can be reduced to the problem of estimating probability distributions of words and ngrams in text. It has become standard practice in text compression, speech recognition, information retrieval and many other applications of Shannon's theory to introduce a “bag-of-words” assumption. But obviously, word rates vary from genre to genre, author to author, topic to topic, document to document, section to section, and paragraph to paragraph. The proposed Poisson mixture captures much of this heterogeneous structure by allowing the Poisson parameter θ to vary over documents subject to a density function φ. φ is intended to capture dependencies on hidden variables such genre, author, topic, etc. (The Negative Binomial is a well-known special case where φ is a Г distribution.) Poisson mixtures fit the data better than standard Poissons, producing more accurate estimates of the variance over documents (σ2), entropy (H), inverse document frequency (IDF), and adaptation (Pr(x ≥ 2/x ≥ 1)).
A rule-based phrase parser for real-time text-to-speech synthesis
Authors: Bachenko Joan , Fitzpatrick Eileen , Daugherty Jeffrey
Published: September 2008

Text-to-speech systems are currently designed to work on complete sentences and paragraphs, thereby allowing front end processors access to large amounts of linguistic context. Problems with this design arise when applications require text to be synthesized in near real time, as it is being typed. How does the system decide which incoming words should be collected and synthesized as a group when prior and subsequent word groups are unknown? We describe a rule-based parser that uses a three cell buffer and phrasing rules to identify break points for incoming text. Words up to the break point are synthesized as new text is moved into the buffer; no hierarchical structure is built beyond the lexical level. The parser was developed for use in a system that synthesizes written telecommunications by Deaf and hard of hearing people. These are texts written entirely in upper case, with little or no punctuation, and using a nonstandard variety of English (e.g.WHEN DO I WILL CALL BACK YOU). The parser performed well in a three month field trial utilizing tens of thousands of texts. Laboratory tests indicate that the parser exhibited a low error rate when compared with a human reader.
Russian morphology: An engineering approach
Authors: Mikheev Andrei , Liubushkina Liubov
Published: September 2008

Morphological analysis, which is at the heart of the processing of natural language requires computationally effective morphological processors. In this paper an approach to the organization of an inflectional morphological model and its application for the Russian language are described. The main objective of our morphological processor is not the classification of word constituents, but rather an efficient computational recognition of morpho-syntactic features of words and the generation of words according to requested morpho-syntactic features. Another major concern that the processor aims to address is the ease of extending the lexicon. The templated word-paradigm model used in the system has an engineering flavour: paradigm formation rules are of a bottom-up (word specific) nature rather than general observations about the language, and word formation units are segments of words rather than proper morphemes. This approach allows us to handle uniformly both general cases and exceptions, and requires extremely simple data structures and control mechanisms which can be easily implemented as a finite-state automata. The morphological processor described in this paper is fully implemented for a substantial subset of Russian (more then 1,500,000 word-tokens – 95,000 word paradigms) and provides an extensive list of morpho-syntactic features together with stress positions for words utilized in its lexicon. Special dictionary management tools were built for browsing, debugging and extension of the lexicon. The actual implementation was done in C and C++, and the system is available for the MS-DOS, MS-Windows and UNIX platforms.
A hierarchical Dirichlet language model
Authors: MacKay David J. C. , Peto Linda C. Bauman
Published: September 2008

We discuss a hierarchical probabilistic model whose predictions are similar to those of the popular language modelling procedure known as ‘smoothing’. A number of interesting differences from smoothing emerge. The insights gained from a probabilistic view of this problem point towards new directions for language modelling. The ideas of this paper are also applicable to other problems such as the modelling of triphomes in speech, and DNA and protein sequences in molecular biology. The new algorithm is compared with smoothing on a two million word corpus. The methods prove to be about equally accurate, with the hierarchical model using fewer computational resources.
High speed feature unification and parsing
Authors: Brown John C.
Published: September 2008

Feature unification in parsing has previously used either inefficient Prolog programs, or LISP programs implementing early pre-WAM Prolog models of unification involving searches of binding lists, and the copying of rules to generate edges: features within rules and edges have traditionally been expressed as lists or functions, with clarity being preferred to speed of processing. As a result, parsing takes about 0·5 seconds for a 7-word sentence. Our earlier work produced an optimised chart parser for a non-unification context-free-grammar that achieved 5 ms parses, with high-ambiguity sentences involving hundreds of edges, using the grammar and sentences from Tomita's work on shift-reduce parsing with multiple stack branches. A parallel logic card design resulted that would speed this by a further factor of at least 17. The current paper extends this parser to treat a much more complex unification grammar with structures, using extensive indexing of rules and edges and the optimisations of top-down filtering and look-ahead, to demonstrate where unification occurs during parsing. Unification in parsing is distinguished from that in Prolog, and four alternative schemes for storing features and performing unification are considered, including the traditional binding-list method and three other methods optimised for speed for which overall unification times are calculated. Parallelisation of unification using cheap logic hardware is considered, and estimates show that unification will negligibly increase the parse time of our parallel parser card. Preliminary results are reported from a prototype serial parser that uses the fourth most efficient unification method, and achieves 7 ms for 7-word sentences, and under 1 s for a 36-word 360-way ambiguous sentence with 10,000 edges, on a conventional workstation.
Engineering “word experts” for word disambiguation
Authors: Berleant Daniel
Published: September 2008

Every word in the lexicon of a natural language is used distinctly from all the other words. A word expert is a small expert system-like module for processing a particular word based on other words in its vicinity. A word expert exploits the idiosyncratic nature of a word by using a set of context testing decision rules that test the identity and placement of context words to infer the word's role in the passage.

The main application of word experts is disambiguating words. Work on word experts has never fully recognized previous related work, and a comprehensive review of that work would therefore contribute to the field. This paper both provides such a review, and describes guidelines and considerations useful in the design and construction of word expert based systems.
Middle English case loss and the ‘creolization’ hypothesis
Authors: Allen Cynthia
Published: September 2008

The apparent rapidity of the loss of case-marking distinctions in English has been used as evidence that Middle English was a Creole. However, an examination of the available facts indicates that the reduction of case marking was more gradual and orderly than has often been assumed. The impression of ‘confused’ usage in many texts disappears once a proper distinction between form and category is made. The reduction of case marking seems to have begun with syncretism of forms but retention of categories, with one form spreading into the territory of another. The facts do not support the idea that case marking was drastically reduced as part of the formation of a Creole. However, it is likely that language contact played a significant role in the quick acceptance of internally motivated changes.
The discourse markerwellin the history of English
Authors: Jucker Andreas H.
Published: September 2008

The discourse markerwellhas four distinct uses in Modern English: as a frame it introduces a new topic or prefaces direct reported speech; as a qualifier it prefaces a reply which is only a partial answer to a question; as a face-threat mitigator it prefaces a disagreement; and as a pause filler it bridges interactional silence.

In Old Englishwellwas used on an interpersonal level as an emphatic attention-getting device (similar to Old Englishhwæt‘listen’, ‘behold’, or ‘what’). In Middle English,wellalways functioned as a frame on a textual level. In Early Modern English, and particularly in the plays by Shakespeare, the uses ofwelldiversified considerably and adopted interpersonal uses again.
Relativethatand prepositional complementation
Authors: Seppänen Aimo
Published: September 2008

Ever since the days of Jespersen, voices have been raised which argue that relativethatis not a pronoun likewhoandwhich, but a conjunction/complementizer, as shown in particular by the ban on the sequence preposition +that, which is claimed to be best described by treatingthatas a conjunction. Taking up the question of the proper analysis ofthatas it appears in the word's relationship to prepositions, the present paper argues that in actual fact the descriptions built by Jespersen and various generative grammarians on the view ofthatas a conjunction/complementizer are not at all adequate to deal with some crucial facts of the word's syntax. Noting then some further facts which even the traditional ban is unable to deal with, the paper develops a new approach to the question which is derived from an examination of Finnish relatives and which handles all the English facts noted in terms of a general principle about the internal order of elements within the fronted relative phrase. The principle invoked is completely neutral as regards the word-class status ofthat, but some of the facts explored strongly argue for the classification of the word as a pronoun.
The influence of formality and channel on relative pronoun choice in New Zealand English
Authors: Sigley Robert
Published: September 2008

This paper describes the effects of text formality and channel on relativizer choice in data from three corpora of written and spoken New Zealand English.Thatand the null relativizer Ø are typically regarded as intrinsically less formal than thewh-pronouns; but are they in fact commoner in spoken/informal texts? If so, is this a direct response to formality? Do prescriptions influence relativizer choice in written/formal texts? These questions are addressed by identifying and controlling significant linguistic influences on relativizer choice, and comparing results for text categories representing a range of formality levels from both channels.