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.

Stress induced phase transition in monomolecular perfluroalkylsilane film self assembled on aluminium surface

We control the stiffnesses of two dual double cantelevers placed in series to control penetration into a perflurooctyltrichlorosilane monolayer self assembled on aluminium and silicon substrates. The top cantilever which carries the probe is displaced with respect to the bottom cantilever which carries the substrate, the difference in displacement recorded using capacitors gives penetration. We further modulate the input displacement sinusoidally to deconvolute the viscoelastic properties of the monolayer. When the intervention is limited to the terminal end of the molecule there is a strong viscous response in consonance with the ability of the molecule to dissipate energy by the generation of gauche defects freely. When the intervention reaches the backbone, at a contact mean pressure of 0.2GPa the damping disappears abruptly and the molecule registers a steep rise in elastic modulus and relaxation time constant, with increasing contact pressure. We offer a physical explanation of the process and describe this change as due to a phase transition from a liquid like to a solid like state.

Self assessment schemes for multi-agent cooperative search

In this paper, we present self assessment schemes (SAS) for multiple agents performing a search mission on an unknown terrain. The agents are subjected to limited communication and sensor ranges. The agents communicate and coordinate with their neighbours to arrive at route decisions. The self assessment schemes proposed here have very low communication and computational overhead. The SAS also has attractive features like scalability to large number of agents and fast decision-making capability. SAS can be used with partial or complete information sharing schemes during the search mission. We validate the performance of SAS using simulation on a large search space consisting of 100 agents with different information structures and self assessment schemes. We also compare the results obtained using SAS with that of a previously proposed negotiation scheme. The simulation results show that the SAS is scalable to large number of agents and can perform as good as the negotiation schemes with reduced communication requirement (almost 20% of that required for negotiation).

Size effect in self consolidating concrete beams with and without notches

The aim of this study is to obtain the fracture characteristics of low and medium compressive strength self consolidating concrete (SCC) for notched and un-notched plain concrete beams by using work of fracture G(F) and size effect model G(f) methods and comparing them with those of normal concrete and high performance concrete. The results show that; (i) with an increase in compressive strength, G(F) increases and G(f) decreases; (ii) with an increase in depth of beam, the decrease in nominal stress of notched beam is more when compared with that of a notchless beam.

A self-consistent formulation for analysis and generation of non-uniform DNA structure

A fully self-consistent formulation is described here for the analysis and generation of base-pairs in non-uniform DNA structures, in terms of various local parameters. It is shown that the internal "wedge parameters" are mathematically related to the parameters describing the base-pair orientation with respect to an external helix axis. Hence any one set of three translation and three rotation parameters are necessary and sufficient to completely describe the relative orientation of the base-pairs comprising a step (or doublet). A general procedure is outlined for obtaining an average or global helix axis from the local helix axes for each step. A graphical representation of the local helix axes in the form of a polar plot is also shown and its application for estimating the curvature of oligonucleotide structures is illustrated, with examples of both A and B type structures.

Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Let G - (V, E) be a weighted undirected graph having nonnegative edge weights. An estimate (delta) over cap (u, v) of the actual distance d( u, v) between u, v is an element of V is said to be of stretch t if and only if delta(u, v) <= (delta) over cap (u, v) <= t . delta(u, v). Computing all-pairs small stretch distances efficiently ( both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24].

A Pd-6 Molecular Cage via Multicomponent Self-Assembly Incorporating Both Neutral and Anionic Linkers

A Pd-6 molecular cage [{(tmen)Pd}(6)(bpy)(3)(tma)2)](NO3)(6) [1; where tmen = N,N,N,N-tetramethylethylene diamine, bpy = 4,4'-bipyridyl,and H(3)tma = trimesic acid] was prepared via the template-free three-component seff-assembly of a cis-blocked palladium(II) acceptorin combination with a tricarboxylate and a dipyridyl donor. Complex 1 represents the first example of a 3D palladium(II) cage of defined shape incorporating anionic and neutral linkers. Guest-induced exclusive formation of this cage was also monitored by an NMR study.

Photoluminescence spectroscopy and lifetime measurements from self-assembled semiconductor-metal nanoparticle hybrid arrays

We present results of photoluminescence spectroscopy and lifetime measurements on thin film hybrid arrays of semiconductor quantum dots and metal nanoparticles embedded in a block copolymer template. The intensity of emission as well as the measured lifetime would be controlled by varying the volume fraction and location of gold nanoparticles in the matrix. We demonstrate the ability to both enhance and quench the luminescence in the hybrids as compared to the quantum dot array films while simultaneously engineering large reduction in luminescence lifetime with incorporation of gold nanoparticles. (C) 2010 American Institute of Physics. [doi:10.1063/1.3483162].

Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Controlled photoluminescence from self-assembled semiconductor-metal quantum dot hybrid array films

Thin films of hybrid arrays of cadmium selenide quantum dots and polymer grafted gold nanoparticles have been prepared using a BCP template. Controlling the dispersion and location of the respective nanoparticles allows us to tune the exciton-plasmon interaction in such hybrid arrays and hence control their optical properties. The observed photoluminescence of the hybrid array films is interpreted in terms of the dispersion and location of the gold nanoparticles and quantum dots in the block copolymer matrix.

Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Self-assembled flower-like nanostructures of InN and GaN grown by plasma-assisted molecular beam epitaxy

Nanosized hexagonal InN flower-like structures were fabricated by droplet epitaxy on GaN/Si(111) and GaN flower-like nanostructure fabricated directly on Si(111) substrate using radio frequency plasma-assisted molecular beam epitaxy. Powder X-ray diffraction (XRD) and scanning electron microscopy (SEM) were used to study the crystallinity and morphology of the nanostructures. Moreover, X-ray photoelectron spectroscopy (XPS) and photoluminescence (PL) were used to investigate the chemical compositions and optical properties of nano-flowers, respectively. Activation energy of free exciton transitions in GaN nano-flowers was derived to be similar to 28.5 meV from the temperature dependent PL studies. The formation process of nano-flowers is investigated and a qualitative mechanism is proposed.

Impact of energy quantisation in single electron transistor island on hybrid complementary metal oxide semiconductor-single electron transistor integrated circuits

For the first time, the impact of energy quantisation in single electron transistor (SET) island on the performance of hybrid complementary metal oxide semiconductor (CMOS)-SET transistor circuits has been studied. It has been shown through simple analytical models that energy quantisation primarily increases the Coulomb Blockade area and Coulomb Blockade oscillation periodicity of the SET device and thus influences the performance of hybrid CMOS-SET circuits. A novel computer aided design (CAD) framework has been developed for hybrid CMOS-SET co-simulation, which uses Monte Carlo (MC) simulator for SET devices along with conventional SPICE for metal oxide semiconductor devices. Using this co-simulation framework, the effects of energy quantisation have been studied for some hybrid circuits, namely, SETMOS, multiband voltage filter and multiple valued logic circuits. Although energy quantisation immensely deteriorates the performance of the hybrid circuits, it has been shown that the performance degradation because of energy quantisation can be compensated by properly tuning the bias current of the current-biased SET devices within the hybrid CMOS-SET circuits. Although this study is primarily done by exhaustive MC simulation, effort has also been put to develop first-order compact model for SET that includes energy quantisation effects. Finally, it has been demonstrated that one can predict the SET behaviour under energy quantisation with reasonable accuracy by slightly modifying the existing SET compact models that are valid for metallic devices having continuous energy states.