Novel melody line identification algorithm for polyphonic MIDI music

The problem of automatic melody line identification in a MIDI file plays an important role towards taking QBH systems to the next level. We present here, a novel algorithm to identify the melody line in a polyphonic MIDI file. A note pruning and track/channel ranking method is used to identify the melody line. We use results from musicology to derive certain simple heuristics for the note pruning stage. This helps in the robustness of the algorithm, by way of discarding "spurious" notes. A ranking based on the melodic information in each track/channel enables us to choose the melody line accurately. Our algorithm makes no assumption about MIDI performer specific parameters, is simple and achieves an accuracy of 97% in identifying the melody line correctly. This algorithm is currently being used by us in a QBH system built in our lab.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Ethyl 6-chloro-2-[(2-chloro-7,8-dimethylquinolin-3-yl)methoxy]-4-phenylquino line-3-carboxylate

In the title compound, C30H24Cl2N2O3, the two quinoline ring systems are almost planar [maximum deviations = 0.029 (2) and 0.018 (3) angstrom] and the dihedral angle between them is 4.17 (8)degrees. The dihedral angle between the phenyl ring and its attached quinoline ring is 69.06 (13)degrees. The packing is stabilized by C-H center dot center dot center dot O, C-H center dot center dot center dot N, weak pi-pi stacking [centroid-centroid distances = 3.7985 (16) and 3.7662(17) angstrom] and C-H center dot center dot center dot pi interactions.

Analysis of shore line protection works in tsunami hit areas of east coast of India

Evaluation and design of shore protection works in the case of tsunamis assumes considerable importance in view of the impact it had in the recent tsunami of 26th December 2004 in India and other countries in Asia. The fact that there are no proper guidelines have made in the matters worse and resulted in the magnitude of damage that occurred. Survey of the damages indicated that the scour as a result of high velocities is one of the prime reasons for damages in the case of simple structures. It is revealed that sea walls in some cases have been helpful to minimize the damages. The objective of this paper is to suggest that design of shore line protection systems using expected wave heights that get generated and use of flexible systems such as geocells is likely to give a better protection. The protection systems can be designed to withstand the wave forces that corresponding to different probabilities of incidence. A design approach of geocells protection system is suggested and illustrated with reference to the data of wave heights in the east coast of India.

Support vector machine approach for the switching transient peak overvoltages during line energization

At the time of restoration transmission line switching is one of the major causes, which creates transient overvoltages. Though detailed Electro Magnetic Transient studies are carried out extensively for the planning and design of transmission systems, such studies are not common in a day-today operation of power systems. However it is important for the operator to ensure during restoration of supply that peak overvoltages resulting from the switching operations are well within safe limits. This paper presents a support vector machine approach to classify the various cases of line energization in the category of safe or unsafe based upon the peak value of overvoltage at the receiving end of line. Operator can define the threshold value of voltage to assign the data pattern in either of the class. For illustration of proposed approach the power system used for switching transient peak overvoltages tests is a 400 kV equivalent system of an Indian southern gri

Boxicity and cubicity of asteroidal triple free graphs

The boxicity of a graph G, denoted box(G), is the least integer d such that G is the intersection graph of a family of d-dimensional (axis-parallel) boxes. The cubicity, denoted cub(G), is the least dsuch that G is the intersection graph of a family of d-dimensional unit cubes. An independent set of three vertices is an asteroidal triple if any two are joined by a path avoiding the neighbourhood of the third. A graph is asteroidal triple free (AT-free) if it has no asteroidal triple. The claw number psi(G) is the number of edges in the largest star that is an induced subgraph of G. For an AT-free graph G with chromatic number chi(G) and claw number psi(G), we show that box(G) <= chi(C) and that this bound is sharp. We also show that cub(G) <= box(G)([log(2) psi(G)] + 2) <= chi(G)([log(2) psi(G)] + 2). If G is an AT-free graph having girth at least 5, then box(G) <= 2, and therefore cub(G) <= 2 [log(2) psi(G)] + 4. (c) 2010 Elsevier B.V. All rights reserved.

Fine Structure of the Rayleigh Line in Amorphous Substances

As is well known, when monochromatic light scattered by a liquid is examined under high resolution it exhibits a fine structure: an undisplaced central line and two lines on either side with wavelengths slightly different from that of the incident light. The appearance of the displaced components was first predicted by Brillouin1. On the basis of his theory, the observed displacements of frequency are regarded as a Doppler effect arising from the reflexion of the light wave by the progressive sound waves of thermal origin in the scattering medium. The frequency shift of the so-called Brillouin components is given by the formula where nu and c are the velocities of sound and light in the medium and theta is the angle of scattering. That the effect contemplated by Brillouin does arise in liquids and crystals is now a well-established experimental fact.

Vibration of simply-supported trapezoidal plates I. Symmetric trapezoids

A detailed investigation of the natural frequencies and mode shapes of simply supported symmetric trapezoidal plates is undertaken in this paper. For numerical calculations, the relationship that exists between the eigenvalue problem of a polygonal simply supported plate and the eigenvalue problem of polygonal membrane of the same shape is utilized with advantage. The deflection surface is expressed in terms of a Fourier sine series in transformed coordinates and the Galerkin method is used. Results are presented in the form of tables and graphs. Several features like the crossing of frequency curves and the metamorphosis of some of the nodal patterns are observed. By a suitable interpretation of the modes of those symmetric trapezoidal plates which have the median as the nodal line, the results for some of the modes of unsymmetrical trapezoidal plates are also deduced.

The Line Spectral Frequency Model of a Finite-Length Sequence

The line spectral frequency (LSF) of a causal finite length sequence is a frequency at which the spectrum of the sequence annihilates or the magnitude spectrum has a spectral null. A causal finite-length sequencewith (L + 1) samples having exactly L-LSFs, is referred as an Annihilating (AH) sequence. Using some spectral properties of finite-length sequences, and some model parameters, we develop spectral decomposition structures, which are used to translate any finite-length sequence to an equivalent set of AH-sequences defined by LSFs and some complex constants. This alternate representation format of any finite-length sequence is referred as its LSF-Model. For a finite-length sequence, one can obtain multiple LSF-Models by varying the model parameters. The LSF-Model, in time domain can be used to synthesize any arbitrary causal finite-length sequence in terms of its characteristic AH-sequences. In the frequency domain, the LSF-Model can be used to obtain the spectral samples of the sequence as a linear combination of spectra of its characteristic AH-sequences. We also summarize the utility of the LSF-Model in practical discrete signal processing systems.

A new class of separators and planarity of chordal graphs

We introduce a new class of clique separators, called base sets, for chordal graphs. Base sets of a chordal graph closely reflect its structure. We show that the notion of base sets leads to structural characterizations of planar k-trees and planar chordal graphs. Using these characterizations, we develop linear time algorithms for recognizing planar k-trees and planar chordal graphs. These algorithms are extensions of the Lexicographic_Breadth_First_Search algorithm for recognizing chordal graphs and are much simpler than the general planarity checking algorithm. Further, we use the notion of base sets to prove the equivalence of hamiltonian 2-trees and maximal outerplanar graphs.

Positional dependence of material flow in friction stir welding: analysis of joint line remnant and its relevance to dissimilar metal welding

Understanding material flow in friction stir welding is important for production of sound dissimilar metal welding that control the intermixing of two alloys being welded and consequent formation of new constituents which influences the weld properties. In the present experimental investigation material flow patterns are visualised using dissimilar and similar aluminium alloys using a simple innovative ,experiment. The experimental results reveal that only a portion of material transported from the leading edge undergoes chaotic flow and the remaining is deposited systematically in the trailing edge of the weld. Using this information it is shown that the formation of a friction stir welding defect, joint line remnant, does not occur only when the weld interface is on the advancing side. The material flow visualisation study has been utilised to analyse the mechanism of weld formation and its usefulness in improving fatigue properties and for dissimilar metal welds.

On the complexity of finding stopping set size in Tanner Graphs

The problem of determining whether a Tanner graph for a linear block code has a stopping set of a given size is shown to be NT-complete.

Generators contribution towards loads and line flows - A case study

n many parts of the world, the goal of electricity supply industries is always the introduction of competition and a lowering of the average consumer price. Because of this it has become much more important to be able to determine which generators are supplying a particular load, how much use each generator is making of a transmission line and what is generator's contribution to the system losses. In this paper a case study on generator contributions towards loads and transmission flows are illustrated with an equivalent 11-bus system, a part of Indian Southern Grid, based on the concepts of circuit flow directions, for normal and network contingency conditions.

Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Computing complete test graphs for hierarchical systems

Conformance testing focuses on checking whether an implementation. under test (IUT) behaves according to its specification. Typically, testers are interested it? performing targeted tests that exercise certain features of the IUT This intention is formalized as a test purpose. The tester needs a "strategy" to reach the goal specified by the test purpose. Also, for a particular test case, the strategy should tell the tester whether the IUT has passed, failed. or deviated front the test purpose. In [8] Jeron and Morel show how to compute, for a given finite state machine specification and a test purpose automaton, a complete test graph (CTG) which represents all test strategies. In this paper; we consider the case when the specification is a hierarchical state machine and show how to compute a hierarchical CTG which preserves the hierarchical structure of the specification. We also propose an algorithm for an online test oracle which avoids a space overhead associated with the CTG.