bluuebunny/crossref_metadata_2025 huggingface dataset:
Contemporary History in Germany after 1989
Authors: Klessmann Christoph , Sabrow Martin
Published: September 2008

In 1953 Hans Rothfels gave a definition of what he understood as contemporary history which rapidly became a classic: ‘the era of those living and its treatment by academics’. In so doing he opened up a field of enquiry to historical scholarship in Germany which had had a long tradition, but which had been almost completely excluded from the discipline since the nineteenth century. In 1821 Wilhelm von Humboldt had declared that ‘chronicling the present’ furnished the ‘necessary basis of history’, but was not ‘history itself’. This paved the way for criticism which, with Leopold von Ranke, increasingly excluded contemporary history from the sphere of academic consideration on the grounds that its typical ‘lack of reliable knowledge’ and ‘conflicts between contemporaries’ impeded objective judgement. Heinrich von Treitschke's dismissive assertion that the most recent past could only be looked at through the biased glasses of a ‘dual partiality’ was only confirmed by a new flourishing ofhistoria sui temporisafter 1914. Thus, as early as the third year of the First World War, theHistorische Zeitschrift(HZ) was talking about the ‘pre-history of the World War’, thereby justifying the verdict that ‘it was practically patriotic rather than academically legitimate’. The same could be said of the notions the historical discipline put forward after 1918 against the ‘Versailles lies about war guilt’.
The Politics of Artistic Identity: the Czech Art World in the 1950s and 1960s
Authors: Svašek Maruška
Published: September 2008

Since the Czech 'revivalist' movement of the last century, Czech art – along with the roles assigned to its artists – has been undergoing a continual process of definition and redefinition. The question of what constituted and what should constitute Czech artistic identity has often proved politically charged, with artists and art historians on opposing sides attacking each other for their political views. More often than not, debates on the issue have been part and parcel of wider social contexts in which artists and art historians have competed for influential positions and artistic prestige within the art world itself.
Liturgical chant bibliography 2
Authors: Jeffery Peter
Published: September 2008

Last year's instalment of ‘Liturgical Chant Bibliography’ was enthusiastically received by many, and I am grateful to all who sent me information about their new publications. I hope you will continue to do so; every publication likely to be of interest to chant scholars is eligible for inclusion.
Anti-semitism in an early fifteenth-century motet: Tu, nephanda
Authors: Lewis Ann
Published: September 2008

There is much interest at present in the way medieval motets generate meaning, both with their texts and their music. In two articles from a recent issue of Early Music History, for example, a remarkable density of meaning and symbolism, both textual and musical, has been proposed for Machaut's motet 15. Studies of this kind are intended to demonstrate what can be achieved by placing the poems of motets in a literary context and by considering the structure of words and music. Such research also no doubt serves to reinforce the idea that many motets of the fourteenth and fifteenth centuries demand a wealth of erudite knowledge to be understood and is thus congenial to the current belief that many motets were intended for an intellectual elite. Whilst there can be no doubt that medieval motets often cultivate a literary style of considerable – indeed intense – obscurity, what I wish to suggest here is that one, very ambitious, motet can be interpreted using some of the most basic tools of the medieval cleric.
The Byzantine prokeimena
Authors: Harris Simon
Published: September 2008

It is possible to attach too much significance to the names of both the hypakoae and the prokeimena. The word ‘hypakoe’ means ‘respond’, but this by itself does not mean that the Byzantine hypakoae were chants that derived from responsorially performed psalms (even though that is what they may ultimately have been), for the name might well refer simply to a responsorial method of singing them which, evidence suggests, prevailed between the eleventh and thirteenth centuries.
John Blitheman's keyboard plainsongs: another ‘kind’ of composition?
Authors: Irving John
Published: September 2008

The foregoing quotation from an epitaph in the church of St Nicholas Olave, Queenhithe, summarizes most of what we know about the career of John Blitheman (c. 1525–91), one of the composers of keyboard plainsong settings represented in the so-called Mulliner Book, compiled probably in London sometime between the mid-1550s and about 1570. All but one of Blitheman's surviving keyboard works is contained in this manuscript.
Bien me sui aperceuz: monophonic chanson and motetus
Authors: Atchison Mary
Published: September 2008

Borrowing or quoting from the trouvère repertory has long been acknowledged as part of the craft of the composers of the thirteenth-century motet. Single strophes from a few trouvère chansons can be found as complete motet voices; partial strophes frame newly composed text and music in motets-entés, and many textual themes and motifs, melodic motifs and refrains can be traced to trouvère sources. Whilst this practice of borrowing can be identified because of the common texts and melodies, or texts or melodies alone, it is difficult to say to what extent other compositional practices, not dependent upon direct quotation, might have found their source and inspiration in the trouvère repertory. An examination of the monophonic chanson Bien me sui aperceuz, and the three-voice motet Se valours / Bien me sui apercheus / Hie factus est, reveals a web of interrelationships between the chanson and the motet which appears far more subtle than the practice of direct borrowing briefly mentioned above. The cryptic clues to these concealed relationships between the chanson and the motet can be found in their texts, whilst the solution is revealed in their melodies.
Authenticity and ‘auteur’: the songs of Hugues de Berzé
Authors: McAlpine Fiona
Published: September 2008

The concept of individual authorship, let alone authorial style, is not one that medievalists are accustomed to dealing with, particularly in the realm of monophonic music. Within this field, however, troubadour and trouvère songs provide a peculiar and almost unique challenge because many of the songs are by identified and identifiable composers. However, between the lives of those composers and the written records of their composition there is a gap which can be almost as long as 200 years. We do not know who compiled the manuscripts, nor do we know why they were produced; but what is plain is that the lines of transmission from composer to written record were neither clear nor simple, given the number and scope of the variants from one manuscript to the next. The relationship between the manuscripts is complex, and stemmatics has not proved particularly useful in determining the variant closest to the composer’s ‘original’. In these circumstances it is hardly surprising that the authentic voice of the composer is not a common subject for discussion. Like other monophonic repertories, the songs of the troubadours and trouvères tend to be analysed as a corpus, and rightly so. If analysis is to encompass the entire legacy of songs, it needs systematic tools of the kind and quality available to other repertories. However, effective tools for the melodic analysis of troubadour and trouvère song are few, for reasons which I have discussed elsewhere.
Signature-systems and tonal types in the fourteenth-century French chanson
Authors: Lefferts Peter M.
Published: September 2008

Beyond the standard and familiar theoretical instruction materials on notation and mensuration, on mode and hexachord, and on the rules of two-part counterpoint, information and insight about the techniques of musical composition in the later Middle Ages are hard to come by. From a modern vantage point, medieval music theory leaves many of the questions most interesting to us unanswered. And for our part, too, analysts of chansons and motets have yet to agree on many basic notions about how this music works, and therefore what is most necessary to talk about. It is symptomatic of this state of affairs that articles discussing analytical approaches to early music, even those addressed to specialists, do not start out in medias res but rather must begin with first principles, and that current textbooks ignore or skimp on all but the most superficial aspects of musical style. We need to establish for all genres the paradigms or fundamental givens, the constraints understood at the outset, the range of choices available to the composer.
A newly discovered keyboard source (Gonzalo de Baena's Arte nouamente inuentada pera aprender a tanger, Lisbon, 1540): a preliminary report
Authors: Knighton Tess
Published: September 2008

The discovery of a musical source is always something of an event. This volume of keyboard music dated 1540 and printed in Lisbon was discovered – appropriately for an Iberian source – in 1992 by Alejandro Iglesias who announced his find at a conference held at the Institution ‘Fernando el Católico’ in Zaragoza in the autumn of that year. It was heralded in the Castilian rhetorical style as the ‘discovery of the century’, and it provided a moment of high drama, especially when it became clear from Iglesias's brief description of the source that it included works by Franco-Netherlandish composers such as Josquin, Ockeghem, Compère, Agricola, Caron and Obrecht. The volume is indeed of considerable interest, not only because it offers keyboard intabulations of previously unknown works by both Franco-Netherlandish and Spanish composers, but also because it is the earliest surviving source of keyboard music from the Iberian peninsula and a rare example of printed instrumental music from the first half of the sixteenth century. Manuel Carlos de Brito, making an assessment of Renaissance Portuguese music in 1989, was perfectly justified in thinking that new music sources were unlikely to appear, and that lack of musical texts to confirm or refute the historical context suggested by documents would limit the history of Portuguese music to the realms of speculation. This discovery, surprising though it is, rescues something from that shadowy kingdom.
The ‘modal theory’, fencing, and the death of Aubry
Authors: Haines John
Published: September 2008

On 29 June 1909, a jury of six scholars decreed that Pierre Aubry (1874–1910), in his bookTrouvères et Troubadours, had stolen the ‘modal’ interpretation of medieval monophony from the young doctor Jean-Baptiste Beck (1881–1943). Aubry was to make amends for his plagiarism in two ways: first, by destroying copies of the book's first edition and issuing an emended one; second, by publishing the trial's verdict in twenty scholarly journals at his own cost. An only slightly emendedTrouvères et Troubadoursdid appear the following year (1910), but Aubry failed to publish the jury's verdict in a single journal. A little over a year after the trial, in August of 1910, he died of a fencing wound. The following year, Beck emigrated to the United States.
The Ampleforth fragments: a preliminary survey
Authors: Malcolm Joan
Published: September 2008

The fragments of liturgical music held in the monastic library of Ampleforth Abbey, Yorkshire, consist of thirty-three manuscript parchment leaves of varying sizes, most of which appear to have been used as strengtheners for book bindings.1 It is difficult to determine their provenance but some clues may be found in the variety of their neume styles. Six of the fragments are written with staffless neumes, the rest have staff notation, including eleven leaves from an Office antiphoner. There are also several fragments with square notation in a mensural form. The neume styles indicate a wide time-span, probably from the eleventh century to the mid-fifteenth century. The geographical region suggested by the notation is, for the most part, that of Lorraine and of southern Germany.
Liturgical chant bibliography 7
Authors: Paucker Günther Michael
Published: September 2008

Liturgical chant bibliography 7 continues the new format initiated last year in this journal: editions and facsimile editions; books, reprints; collections of essays, congress reports, chant periodicals, dictionaries; articles in periodicals and Festschriften. This year's bibliography begins with a list of additions to the previous bibliography. In the case of a few titles, the Lexicon Musicum Latinum (7053) or MGG (7059), for example, I have referred to publications listed in LitChBibl 6. Completing and facilitating access to the bibliography are separate indices of names, subjects and manuscripts
Hodie puer natus est nobis:The celebration of Christmas at Piacenza in 1142
Authors: Jensen Brian Mller
Published: September 2008

In the course of a discussion of the Christian liturgy and religious rituals in general, Mircea Eliade maintained that every religious festival, any liturgical time, represents the reactualization of a sacred event that took place in a mythical past, since words and gestures of a ritual are thought to be charged with a power of reactualization so that the event imitated is believed rendered present for the community's welfar. My analysis of the Piacentinian Christmas texts will be based on the phenomenological theories of religion elaborated by Eliade and Odo Casel. It will examine how the medieval Mass was not only a religious ceremony in praise of God but also a cultic experience in terms of the time and space of the ceremony. The liturgical apparatus will be considered as the actual vehicle that creates the proclaimed reality of the celebration, because it is within the power of the Mass to bring us into the same temporal dimension with the saving deeds of Christ and to place us in their immediate presence. By indicating the complexity of dimensions involved in religious practice, its ritual, mythological, doctrinal and experimental aspects, this phenomenological approach to the medieval Christian liturgy implies that thetelosof each individual Mass goes beyond the liturgical celebration itself. It would seem to be of some interest, then, to subject to a detailed investigation those texts that were selected in a specific diocese at a certain time to achieve such atelos.
Prosas for Saint Thomas Becket
Authors: Slocum Kay Brainerd
Published: September 2008

Two decades ago Thomas Forrest Kelly remarked in a footnote to an article concerning responsory prosas that the extent of the repertoire of these additions to the Office can be seen only by surveying large numbers of medieval Office books. In the haystack of a faded thousand-page breviary, he remarked, the needle of a single small prosula can be a real joy! The foundation of this essay is just such a needle, and I hope to employ it to add a few threads to the ever-developing tapestry woven by practitioners of the sister disciplines of history and musicology. My purpose is to present an analysis of a liturgical portrait of Thomas Becket, focusing upon the texts and musical settings of two prosas unique to the British Library manuscript Add.
New tenor sources for fourteenth-century motets
Authors: Clark Alice V.
Published: September 2008

The study of the medieval motet in France has recently been rejuvenated, in part by returning to the motet's point of origin – its tenor. Some scholars have focused on the tenor's pitch content, showing how it shapes the motet's harmonies, and how it is in turn shaped by local chant variants; others, by considering the tenor's text and the origin of that text in the liturgy and frequently in the Bible, have shown the motet to be perhaps the quintessential musical manifestation of medieval intertextuality. By bringing together sacred and secular, Latin and vernacular, the motet, better than any other musical genre, exemplifies both the Boethian ideal of music as something much larger than sound and the interconnectedness of all things in the medieval mind. The discovery of hitherto unknown chant sources for motet tenors is therefore an opportunity to reinterpret the texts of the motets they underpin.
Simon Mellet, scribe of Cambrai Cathedral
Authors: Curtis Liane
Published: September 2008

Simon Mellet, scribe and vicar at the cathedral of Cambrai, is among the best-known music scribes of the fifteenth century. Jules Houdoy's classic study of Cambrai Cathedral (1880) documented numerous payments made to Mellet for copying, payments which have remained an important source of information for our understanding of the career of Guillaume Du Fay and the role of the Cambrai Cathedral as a vital musical centre in the fifteenth century. Simon Mellet's thirty-six-year career dominates the study of the production of music manuscripts at Cambrai. Payments made to Mellet are mentioned in most research on Du Fay and on sacred polyphony in the Franco-Burgundian regions. It is through these documents that we know of lost works by Du Fay, such as the Requiem, and of the existence of the composer Rasse de Lavenne. The payments even tell us of apparently wholly lost genres, such as the lamentations by Busnois, Ockeghem and Fremiet that were copied by Mellet in 1475–6.
Almost all Berge Graphs are Perfect
Authors: Prömel Hans Jürgen , Steger Angelika
Published: September 2008

Let Per f(n) denote the set of all perfect graphs on n vertices and let Berge(n) denote the set of all Berge graphs on n vertices. The strong perfect graph conjecture states that Per f(n) = Berge(n) for all n. In this paper we prove that this conjecture is at least asymptotically true, i.e. we show that
The Computational Complexity of the Tutte Plane: the Bipartite Case
Authors: Vertigan D. L. , Welsh D. J. A.
Published: September 2008

Along different curves and at different points of the (x, y)-plane the Tutte polynomial evaluates a wide range of quantities. Some of these, such as the number of spanning trees of a graph and the partition function of the planar Ising model, can be computed in polynomial time, others are # P-hard. Here we give a complete characterisation of which points and curves are easy/hard in the bipartite case.
On the Diameter of Random Cayley Graphs of the Symmetric Group
Authors: Babai L. , Hetyei G. L.
Published: September 2008

Let σ, π be two permutations selected at random from the uniform distribution on the symmetric group Sn. By a result of Dixon [5], the subgroup G generated by σ, π is almost always (i.e. with probability approaching 1 as n → ∞) either Sn or the alternating group An. We prove that the diameter of the Cayley graph of G defined by {σ, π} is almost always not greater than exp ((½ + o(l)). (In n)2).
A Characterisation of Strict Matching Matroids
Authors: Bryant Victor
Published: September 2008

It is well known that a matroid is a transversal matroid if and only if it is a matching matroid (in the sense that it is the restriction of the matching structure of some graph to a subset of its vertices). A simple proof of that result is now known and in this paper it is used to answer the long-standing question of which transversal matroids are “strict” matching matroids; i.e. actually equal to the matching structure of a graph. We develop a straightforward test of “coloop-surfeit” that can be applied to any transversal matroid, and our main theorem shows that a transversal matroid is a strict matching matroid if and only if it has even rank and coloop-surfeit. Furthermore, the proofs are algorithmic and enable the construction of an appropriate graph from any presentation of a strict matching matroid.
Duality for Random Sequential Adsorption on a Lattice
Authors: Fan Y. , Percus J. K.
Published: September 2008

If particles are dropped randomly on a lattice, with a placement being cancelled if the site in question or a nearest neighbor is already occupied, an ensemble of restricted random walks is created. We seek the time dependence of the expected occupation of a given site. It is shown that this problem reduces to one of enumerating walks from the given site in which a move can only be made to a previously occupied site or one of its nearest neighbors.
On the Thickness of Sparse Random Graphs
Authors: Cooper Colin
Published: September 2008

The thickness of sparse random graphs in the model Gn, p is closely related to the arboricity, provided p(n) is suitably small. This allows us to identify a range of p(n) for which the thickness is approximately np/2.
Sign-Coherent Identities for Characteristic Polynomials of Matroids
Authors: Kung Joseph P. S.
Published: September 2008

We derive an explicit formula for the difference χ(G;λ) − χ(G|X;λ)χ(Tx(G); λ)/(λ − 1), where χ(G;λ) is the characteristic polynomial of a simple matroid G, G|X is the restriction of G to a flat X in G, and Tx(G) is the complete principal truncation of G at the flat X. Two counting proofs of this formula are given. The first uses the critical problem and the second uses the broken-circuit complex. We also derive several inequalities involving Whitney numbers of the first kind and other numerical invariants.
Reconstructing a Graph from its Neighborhood Lists
Authors: Aigner Martin , Triesch Eberhard
Published: September 2008

Associate to a finite labeled graph G(V, E) its multiset of neighborhoods (G) = {N(υ): υ ∈ V}. We discuss the question of when a list is realizable by a graph, and to what extent G is determined by (G). The main results are: the decision problem is NP-complete; for bipartite graphs the decision problem is polynomially equivalent to Graph Isomorphism; forests G are determined up to isomorphism by (G); and if G is connected bipartite and (H) = (G), then H is completely described.
Linear-Time Approximation Algorithms for the Max Cut Problem
Authors: van Ngoc Nguyen , Tuza Zsolt
Published: September 2008

Let G be a connected graph with n vertices and m edges (multiple edges allowed), and let k ≥ 2 be an integer. There is an algorithm with (optimal) running time of O(m) that finds

(i) a bipartite subgraph of G with ≥ m/2 + (n − 1)/4 edges,

(ii) a bipartite subgraph of G with ≥ m/2 + 3(n−1)/8 edges if G is triangle-free,

(iii) a k-colourable subgraph of G with ≥ m − m/k + (n−1)/k + (k − 3)/2 edges if k ≥ 3 and G is not k-colorable.

Infinite families of graphs show that each of those lower bounds on the worst-case performance are best possible (for every algorithm). Moreover, even if short cycles are excluded, the general lower bound of m − m/k cannot be replaced by m − m/k + εm for any fixed ε > 0; and it is NP-complete to decide whether a graph with m edges contains a k-colorable subgraph with more than m − m/k + εm edges, for any k ≥ 2 and ε> 0, ε < 1/k.
Ramsey Problems with Bounded Degree Spread
Authors: Chen G. , Schelp R. H.
Published: September 2008

Let k be a positive integer, k ≥ 2. In this paper we study bipartite graphs G such that, for n sufficiently large, each two-coloring of the edges of the complete graph Kn gives a monochromatic copy of G, with some k of its vertices having the maximum degree of these k vertices minus the minimum degree of these k vertices (in the colored Kn) at most k − 2.
A Zero-Free Interval for Chromatic Polynomials of Graphs
Authors: Jackson Bill
Published: September 2008

LetGbe a graph andP(G, t) be the chromatic polynomial ofG. It is known thatP(G, t) has no zeros in the intervals (−∞, 0) and (0, 1). We shall show thatP(G, t) has no zeros in (1, 32/27]. In addition, we shall construct graphs whose chromatic polynomials have zeros arbitrarily close to 32/27.
(1, 2)-Factorizations of General Eulerian Nearly Regular Graphs
Authors: Häggkvist Roland , Johansson Anders
Published: September 2008

Every general graph with degrees 2k and 2k − 2, k ≥ 3, with zero or at least two vertices of degree 2k − 2 in each component, has a k-edge-colouring such that each monochromatic subgraph has degree 1 or 2 at every vertex.

In particular, if T is a triangle in a 6-regular general graph, there exists a 2-factorization of G such that each factor uses an edge in T if and only if T is non-separating.
How Do Read-Once Formulae Shrink?
Authors: Dubiner Moshe , Zwick Uri
Published: September 2008

Let f be a de Morgan read-once function of n variables. Let fε be the random restriction obtained by independently assigning to each variable of f, the value 0 with probability (1 -ε)/2, the value 1 with the same probability, and leaving it unassigned with probability ε. We show that fε depends, on the average, on only O(εαn + εn1/α) variables, where . This result is asymptotically the tightest possible. It improves a similar result obtained recently by Håstad, Razborov and Yao.
On Brooks' Theorem for Sparse Graphs
Authors: Kim Jeong Han
Published: September 2008

Let G be a graph with maximum degree Δ(G). In this paper we prove that if the girth g(G) of G is greater than 4 then its chromatic number, χ(G), satisfies

where o(l) goes to zero as Δ(G) goes to infinity. (Our logarithms are base e.) More generally, we prove the same bound for the list-chromatic (or choice) number:

provided g(G) < 4.
A Probabilistic Analysis of a String Editing Problem and its Variations
Authors: Louchard Guy , Szpankowski Wojciech
Published: September 2008

We consider a string editing problem in a probabilistic framework. This problem is of considerable interest to many facets of science, most notably molecular biology and computer science. A string editing transforms one string into another by performing a series of weighted edit operations of overall maximum (minimum) cost. The problem is equivalent to finding an optimal path in a weighted grid graph. In this paper we provide several results regarding a typical behaviour of such a path. In particular, we observe that the optimal path (i.e. edit distance) is almost surely (a.s.) equal to αn for large n where α is a constant and n is the sum of lengths of both strings. More importantly, we show that the edit distance is well concentrated around its average value. In the so called independent model in which all weights (in the associated grid graph) are statistically independent, we derive some bounds for the constant α. As a by-product of our results, we also present a precise estimate of the number of alignments between two strings. To prove these findings we use techniques of random walks, diffusion limiting processes, generating functions, and the method of bounded difference.
Proof of a Packing Conjecture of Bollobás
Authors: Komlós János , Sárközy Gábor N. , Szemerédi Endre
Published: September 2008

Béla Bollobás [1] conjectured the following. For any positive integer Δ and real 0 < c < ½ there exists an n0 with the following properties. If n ≥ n0, T is a tree of order n and maximum degree Δ, and G is a graph of order n and maximum degree not exceeding cn, then there is a packing of T and G. Here we prove this conjecture. Auxiliary Theorem 2.1 is of independent interest.
Shortcutting Planar Digraphs
Authors: Thorup Mikkel
Published: September 2008

This paper presents a constructive proof that for any planar digraph G on p vertices, there exists a subset S of the transitive closure of G such that the number of arcs in S is less than or equal to the number of arcs in G, and such that the diameter of G∪S is O(α(p, p)(log p)2). Here the diameter refers to the maximum distance from a vertex υ to a vertex w where (υ, w) is from the transitive closure of G – which is also the transitive closure of G ∪ S. This result provides support for the author's previous conjecture that such a set S achieving a diameter polylogarithmic in the number of vertices exists for any digraph. The result also adresses an open question of Chazelle, who did some related work on trees, and suggested the generalization to the planar cases.
Multivariate Identities, Permutation and Bonferroni Upper Bounds
Authors: Chen Tuhao , Seneta E.
Published: September 2008

We derive identities for the probability that at least a1 and at least a2, and for the probability that exactly a1 and exactly a2, out of n and N events occur (1 ≤ a1 ≤ n, 1 ≤ a2 ≤ N). From this, we produce multivariate permutation hybrid upper bounds, and a multivariate Bonferroni-type upper bound which includes Galambos and Xu's [2] optimal result. The methodology generalizes that of Hoppe and Seneta [3, §5]. A numerical example is given.
On Weighted Sequence Sums
Authors: Hamidoune Yahya Ould
Published: September 2008

The main result of this paper has the following consequence. Let G be an abelian group of order n. Let {xi: 1 ≤ 2n − 1} be a family of elements of G and let {wi: 1 ≤ i ≤ n − 1} be a family of integers prime relative to n. Then there is a permutation & of [1,2n − 1] such that

Applying this result with wi = 1 for all i, one obtains the Erdős–Ginzburg–Ziv Theorem.
Random Regular Graphs: Asymptotic Distributions and Contiguity
Authors: Janson Svante
Published: September 2008

The asymptotic distribution of the number of Hamilton cycles in a random regular graph is determined. The limit distribution is of an unusual type; it is the distribution of a variable whose logarithm can be written as an infinite linear combination of independent Poisson variables, and thus the logarithm has an infinitely divisible distribution with a certain discrete Lévy measure. Similar results are found for some related problems. These limit results imply that some different models of random regular graphs are contiguous, which means that they are qualitatively asymptotically equivalent. For example, if r > 3, then the usual (uniformly distributed) random r-regular graph is contiguous to the one constructed by taking the union of r perfect matchings on the same vertex set (assumed to be of even cardinality), conditioned on there being no multiple edges. Some consequences of contiguity for asymptotic distributions are discussed.
Some Asymptotical Estimates for Planar Eulerian Maps
Authors: Liskovets Valery A.
Published: September 2008

In this paper, asymptotical estimates of the form Rn(1+o(1)) for various classes of planar valency-restricted Eulerian maps are established. It follows, in particular, that ‘almost all’ (as n → ∞) n-edged planar Eulerian maps have n/3 (1+o(1)) vertices. A brief survey of known asymptotical results (a table of values of R) for various classes of planar maps is also presented.
On the Number of Hamiltonian Cycles in Bipartite Graphs
Authors: Thomassen Carsten
Published: September 2008

We prove that a bipartite uniquely Hamiltonian graph has a vertex of degree 2 in each color class. As consequences, every bipartite Hamiltonian graph of minimum degree d has at least 21−dd! Hamiltonian cycles, and every bipartite Hamiltonian graph of minimum degree at least 4 and girth g has at least (3/2)g/8 Hamiltonian cycles. We indicate how the existence of more than one Hamiltonian cycle may lead to a general reduction method for Hamiltonian graphs.
Natural language processing in an operational clinical information system
Authors: Friedman C. , Hripcsak G. , DuMouchel W. , Johnson S. B. , Clayton P. D.
Published: September 2008

This paper describes a natural language text extraction system, called MEDLEE, that has been applied to the medical domain. The system extracts, structures, and encodes clinical information from textual patient reports. It was integrated with the Clinical Information System (CIS), which was developed at Columbia-Presbyterian Medical Center (CPMC) to help improve patient care. MEDLEE is currently used on a daily basis to routinely process radiological reports of patients at CPMC.

In order to describe how the natural language system was made compatible with the existing CIS, this paper will also discuss engineering issues which involve performance, robustness, and accessibility of the data from the end users' viewpoint.

Also described are the three evaluations that have been performed on the system. The first evaluation was useful primarily for further refinement of the system. The two other evaluations involved an actual clinical application which consisted of retrieving reports that were associated with specified diseases. Automated queries were written by a medical expert based on the structured output forms generated as a result of text processing. The retrievals obtained by the automated system were compared to the retrievals obtained by independent medical experts who read the reports manually to determine whether they were associated with the specified diseases. MEDLEE was shown to perform comparably to the experts. The technique used to perform the last two evaluations was found to be a realistic evaluation technique for a natural language processor.
Best parse parsing with Earley's and Inside algorithms on probabilistic RTN
Authors: Han Young S. , Choi Key-Sun
Published: September 2008

Inside parsing is a best parse parsing method based on the Inside algorithm that is often used in estimating probabilistic parameters of stochastic context free grammars. It gives a best parse in O(N3G3) time where N is the input size and G is the grammar size. Earley algorithm can be made to return best parses with the same complexity in N.

By way of experiments, we show that Inside parsing can be more efficient than Earley parsing with sufficiently large grammar and sufficiently short input sentences. For instance, Inside parsing is better with sentences of 16 or less words for a grammar containing 429 states. In practice, parsing can be made efficient by employing the two methods selectively.

The redundancy of Inside algorithm can be reduced by the topdown filtering using the chart produced by Earley algorithm, which is useful in training the probabilistic parameters of a grammar. Extensive experiments on Penn Tree corpus show that the efficiency of Inside computation can be improved by up to 55%.
Aspectuality and countability: a cross-categorial analogy
Authors: Brinton Laurel J.
Published: September 2008

This paper expands the analogy between events and count nouns, and between states/activities and mass nouns in English to include other situation types, including iteratives, habits, and multiple situations. It explores the evidence used to make such analogies, namely, the quantificational features of deverbal nouns, as each of the deverbalizing devices in English has its own aspectual qualities. It shows further that a number of parallels can be drawn between different types of bounding and debounding in the nominal and verbal domains. Finally, the paper presents a schema of the cross-categorial analogies relating to inherent meaning (mass/count features in nouns, situation types in verbs) and the semantic operations of (de)bounding and (de)collectivizing (quantificational and aspectual modification).
When is a sequence of two nouns a compound in English?
Authors: Bauer Laurie
Published: September 2008

Constructions of noun + noun have been treated in two distinct ways in the literature: either they have been treated as compounds, or they have been treated as noun phrases with modifiers which happen to be nouns. Sometimes it is assumed that there are two distinct classes, which can be neatly distinguished. In this paper it is argued that the criteria which are usually assumed to distinguish between these two construction types do not draw a clear and consistent distinction between a syntactic and a morphological construction. Many of the criteria instead are indirect measures of listedness, which, it is argued, is not sufficient to show morphological status. Accordingly, it is claimed that the criteria to which reference is generally made do not allow us to distinguish between a class of noun + noun compounds and a class of noun + noun syntactic constructions. Rather the two should be treated as variants of a single construction (possibly morphological, possibly syntactic), at least until such time as a suitable coherent distinction can be properly motivated.
Developments in argument linking in early Modern English gerund phrases
Authors: Fanego Teresa
Published: September 2008

This paper discusses the internal structure of eModE gerund phrases, with special reference to the verbalization of subjects and objects in the course of the period. It is shown that the gerund's acquisition of common case subjects (‘Johnlooking at me’) and of direct objects (‘by seeingJane’) correlates with style, the new verbalized complements being recorded first in the more oral and informal registers. Attention is also paid to the influence of absolute participles on the replacement of PossPs (‘John'slooking at me’) by NPs as subject arguments, and to the diffusion of direct objects across the various classes of gerunds. The mixed nomino-verbal properties exhibited by many gerundive nominals by the late seventeenth century are considered in detail, and an analysis is proposed which interprets them as determiner phrases (DPs) where the head D can select various categories of complements. Alongside this phrasal type of gerund, it is argued that a clausal one with fully verbal features must also be recognized as part of the grammar of eModE.
Prosodic optimization: the Middle English length adjustment
Authors: Bermúdez-Otero Ricardo
Published: September 2008

During late Old and Middle English, the distribution of short and long vowels in stressed syllables was profoundly altered. The changes involved have traditionally been understood as conspiring to optimize syllable quantity according to the position of the syllable in the word. However, Minkova's reformulation of so-called Middle English Open Syllable Lengthening (MEOSL) as a purely compensatory process appears difficult to reconcile with the traditional approach, which has recently been further compromised by suggestions that Trisyllabic Shortening was not a genuine historical sound change. In this article, Minkova's analysis is supported with new evidence of phonological conditioning behind the irregular lengthening of unapocopated disyllabic stems (e.g.ravenvsheaven, body, gannet). I propose solutions to Riad's ‘data problem’ and ‘analytical problem’. Optimality Theory allows Minkova's revised statement of MEOSL to be integrated into a broader, non-teleological account of late Old and Middle English quantitative developments, including coverage of processes of lexical change such as borrowing and diffusion.
SWINBURNE ON RELIGION AND ETHICS
Authors: Blackburn Simon
Published: September 2008

Simon Blackburn responds to the preceding article by Richard Swinburne.
DOES A BELIEF IN GOD LEAD TO MORAL COWARDICE?: THE DIFFERENCE BETWEEN COURAGE OF MORAL CONVICTION AND ACQUISITION
Authors: Ives Jonathan
Published: September 2008

In our seventh and final piece on the theme “Good without God”, Jonathan Ives argues that reliance on God as an external source of moral authority leads to a kind of moral cowardice.
RETROACTIVE IDENTITY ASCRIPTIONS, EMPTY QUESTIONS, AND INTRINSIC RELATIONS
Authors: Ablondi Fred
Published: September 2008

If a statue and lump of clay have the same life-histories, are they numerically identical?
THINKING TOOLS: SUPPRESSED EVIDENCE
Authors: Law Stephen
Published: September 2008

Thinking tools is a regular feature that offers tips and pointers on thinking clearly and rigorously.
MORALITY WITH AND WITHOUT GOD
Authors: Thomas Terence
Published: September 2008

It began with a lie. Perhaps not a big lie, at least I didn't think so at the time, but a lie nevertheless. My Vicar had taken me for an interview with our Bishop following my application, supported by him, to undergo ordination training. My Vicar had prepared me well except that he never warned me that I would be asked if I was sure that I had a vocation. I had to hazard a guess at what this question meant. I wanted to be a clergyman like the Vicar and I sensed that if I answered: “No”, to the bishop's question, I probably wouldn't be proceeding much further. So I said “Yes”, not really knowing what I was committing myself to. Later I worked out that the question was meant to reassure the bishop that I had had a word from God. At the end, many, many years later, when I admitted to myself that there really wasn't a god, it was the same question that rose up to meet me. By then I had to admit that I had never, ever had a word from God.
Collection and characterization of maize and upland rice populations cropped by poor farmers in the uplands of Panama's Azuero region
Authors: Love B. E. , Dreisigacker S. , Spaner D.
Published: September 2008

The conservation of crop genetic resources is an international priority and requires the continued collection and characterization of farmer varieties. We collected and characterized maize and upland rice populations cropped by farmers in Panama's Azuero region. The objective of our study was to evaluate the crop genetic diversity of farmer varieties of maize and upland rice grown by poor farmers in Panama. We found that: (1) farmers' naming practices only partially corresponded to genetic relationships and were the strongest for rice populations; (2) farmers' classification of populations as ‘modern’ or ‘traditional’ was reflected in phenotypic differences; (3) Panamanian maize populations were molecularly distinct from populations collected elsewhere in Latin America; and (4) heterogeneous rice populations were common and heterogeneity was often due to admixture of recognized farmer varieties. Our results indicate that poor farmers in Panama continue to farm ‘traditional’ varieties that harbour genetic diversity of interest. There has, however, been substantial adoption of ‘modern’ varieties.
Genetic diversity analysis of kenaf ( Hibiscus cannabinus L.) using AFLP (amplified fragment length polymorphism) markers
Authors: Coetzee Rouxlene , Herselman Liezel , Labuschagne Maryke T.
Published: September 2008

Nineteen kenaf genotypes from Cuba, Taiwan, the USA, El Salvador, Guatemala, Russia, Spain and Indonesia, and three wild types collected in South Africa were analysed for genetic diversity using AFLP analysis. All could be uniquely distinguished from one another, but only a low level of genetic diversity was present. The most distinct accession, Guatemala 4, was 85% similar to all other accessions. The accessions clustered more or less according to known pedigree and/or origin. Two of the three wild types (Hibiscus cannabinusc andH. cannabinusa) clustered separately from the commercial and Russian accessions. One of the wild types,H. cannabinusb clustered with some of the commercial accessions. Commercial accessions in the first subgroup all originated from central and North America, and surrounding islands (Cuba and El Salvador). The Russian accessions are all grouped together. The second subgroup was the only group that contained accessions from different geographical origins.
A process‐based diagnostic approach to model evaluation: Application to the NWS distributed hydrologic model
Authors: Yilmaz Koray K. , Gupta Hoshin V. , Wagener Thorsten
Published: September 2008

Distributed hydrological models have the potential to provide improved streamflow forecasts along the entire channel network, while also simulating the spatial dynamics of evapotranspiration, soil moisture content, water quality, soil erosion, and land use change impacts. However, they are perceived as being difficult to parameterize and evaluate, thus translating into significant predictive uncertainty in the model results. Although a priori parameter estimates derived from observable watershed characteristics can help to minimize obstacles to model implementation, there exists a need for powerful automated parameter estimation strategies that incorporate diagnostic information regarding the causes of poor model performance. This paper investigates a diagnostic approach to model evaluation that exploits hydrological context and theory to aid in the detection and resolution of watershed model inadequacies, through consideration of three of the four major behavioral functions of any watershed system; overall water balance, vertical redistribution, and temporal redistribution (spatial redistribution was not addressed). Instead of using classical statistical measures (such as mean squared error), we use multiple hydrologically relevant “signature measures” to quantify the performance of the model at the watershed outlet in ways that correspond to the functions mentioned above and therefore help to guide model improvements in a meaningful way. We apply the approach to the Hydrology Laboratory Distributed Hydrologic Model (HL‐DHM) of the National Weather Service and show that diagnostic evaluation has the potential to provide a powerful and intuitive basis for deriving consistent estimates of the parameters of watershed models.
Relationship between typhoon activity and upper ocean heat content
Authors: Wada A. , Chan J. C. L.
Published: September 2008

A 44‐year mean distribution of tropical cyclone heat potential (TCHP), a measure of the oceanic heat content from the surface to the 26°C‐isotherm depth, shows that TCHP is locally high in the western North Pacific (WNP). TCHP varies on interannual time scales and has a relationship with tropical cyclone (TC) activity. The third mode of an empirical orthogonal function analysis of TCHP shows that an increase in the total number of TCs is accompanied with a warm central Pacific and cool WNP. Negative TCHP anomalies in the WNP suggest that an increase in total number of TCs results in cooling due to their passages. On the other hand, the first mode shows that the number of super typhoons increases in mature El Niño years. An increase in accumulated TCHP is related to the increase in the number of super typhoons due to long duration.
A study of AMSU‐A measurement of brightness temperatures over the ocean
Authors: Mo Tsan , Liu Quanhua
Published: September 2008

Brightness temperatures observed by the NOAA 15, 16, 17, and 18 Advanced Microwave Sounding Unit‐A (AMSU‐A) over the tropical ocean region 20°S–20°N are investigated for the months of January, April, July, and October 2006. Monthly mean angular distributions of the data from each month show a very stable pattern. The two sets of data measured by the NOAA 16 and 18 satellites agree well with each other. It is found that the observed brightness temperatures from the descending passes at local equator crossing time (LECT) 0200 are higher than those of the ascending passes at LECT 1400 in the window channels (i.e., channels 1–3 and 15) even though the sea surface temperatures (SSTs) at ∼1400 LECT are usually warmer than those at ∼0200 LECT. The cause of such surprising observations is attributed to the differences in atmospheric transmittance and ocean surface emissivities. As a function of SST, the ocean surface emissivity increases as the SST decreases and vice versa. It is found that the transmittances at the descending (nighttime) passes are smaller than those at the ascending (daytime) ones and that smaller transmittances enhance the upwelling atmospheric contribution to the brightness temperatures. Angular distributions were simulated with a radiative transfer model of one layer of effective atmosphere with optical depth α and temperatures T0 and TS at the top and bottom of the layer, respectively. A least squares fitting method is used to match the model calculations with the AMSU‐A measurements. The simulated results agree well with all AMSU‐A measurements. The NOAA 16 data can be reproduced with the best fit parameters obtained from the NOAA 18 data. Such a close resemblance and stable pattern of angular distributions from the two satellites are potentially useful for postlaunch calibration of future microwave radiometers. The data from the four satellites with different equator crossing times are used to study the diurnal variation of the ocean surface brightness temperatures, which show patterns of daytime cooling and nighttime warming.