Conflict-Tolerant Real-Time Specifications in Metric Temporal Logic

A framework based on the notion of "conflict-tolerance" was proposed in as a compositional methodology for developing and reasoning about systems that comprise multiple independent controllers. A central notion in this framework is that of a "conflict-tolerant" specification for a controller. In this work we propose a way of defining conflict-tolerant real-time specifications in Metric Interval Temporal Logic (MITL). We call our logic CT-MITL for Conflict-Tolerant MITL. We then give a clock optimal "delay-then-extend" construction for building a timed transition system for monitoring past-MITL formulas. We show how this monitoring transition system can be used to solve the associated verification and synthesis problems for CT-MITL.

Geochemistry of water and ground water in the Nhecolandia, Pantanal of Mato Grosso, Brazil: Variability and associated processes

A distinctive feature of the Nhecolandia, a sub-region of the Pantanal wetland in Brazil, is the presence of both saline and freshwater lakes. Saline lakes used to be attributed to a past and phase during the Pleistocene. However, recent studies have shown that saline and fresh water lakes are linked by a continuous water table, indicating that saline water could come from a contemporary concentration process. This concentration process could also be responsible for the large chemical variability of the waters observed in the area. A regional water sampling has been conducted in surface and sub-surface water and the water table, and the results of the geochemical and statistical analysis are presented. Based on sodium contents, the concentration shows a 1: 4443 ratio. All the samples belong to the same chemical family and evolve in a sodic alkaline manner. Calcite or magnesian calcite precipitates very early in the process of concentration, probably followed by the precipitation of magnesian silicates. The most concentrated solutions remain under-saturated with respect to the sodium carbonate salt, even if this equilibrium is likely reached around the saline lakes. Apparently, significant amounts of sulfate and chloride are lost simultaneously from the solutions, and this cannot be explained solely by evaporative concentration. This could be attributed to the sorption on reduced minerals in a green sub-surface horizon in the "cordilhieira" areas. In the saline lakes, low potassium, phosphate, magnesium, and sulfate are attributed to algal blooms. Under the influence of evaporation, the concentration of solutions and associated chemical precipitations are identified as the main factors responsible for the geochemical variability in this environment (about 92 % of the variance). Therefore, the saline lakes of Nhecolandia have to be managed as landscape units in equilibrium with the present water flows and not inherited from a past and phase. In order to elaborate hydrochemical tracers for a quantitative estimation of water flows, three points have to be investigated more precisely: (1) the quantification of magnesium involved in the Mg-calcite precipitation; (2) the identification of the precise stoichiometry of the Mg-silicate; and (3) the verification of the loss of chloride and sulfate by sorption onto labile iron minerals.

Partial instantiation methods for inference in first-order logic

Satisfiability algorithms for propositional logic have improved enormously in recently years. This improvement increases the attractiveness of satisfiability methods for first-order logic that reduce the problem to a series of ground-level satisfiability problems. R. Jeroslow introduced a partial instantiation method of this kind that differs radically from the standard resolution-based methods. This paper lays the theoretical groundwork for an extension of his method that is general enough and efficient enough for general logic programming with indefinite clauses. In particular we improve Jeroslow's approach by (1) extending it to logic with functions, (2) accelerating it through the use of satisfiers, as introduced by Gallo and Rago, and (3) simplifying it to obtain further speedup. We provide a similar development for a "dual" partial instantiation approach defined by Hooker and suggest a primal-dual strategy. We prove correctness of the primal and dual algorithms for full first-order logic with functions, as well as termination on unsatisfiable formulas. We also report some preliminary computational results.

The repertoire of protein kinases encoded in the draft version of the human genome: atypical variations and uncommon domain combinations

Background: Phosphorylation by protein kinases is central to cellular signal transduction. Abnormal functioning of kinases has been implicated in developmental disorders and malignancies. Their activity is regulated by second messengers and by the binding of associated domains, which are also influential in translocating the catalytic component to their substrate sites, in mediating interaction with other proteins and carrying out their biological roles. Results: Using sensitive profile-search methods and manual analysis, the human genome has been surveyed for protein kinases. A set of 448 sequences, which show significant similarity to protein kinases and contain the critical residues essential for kinase function, have been selected for an analysis of domain combinations after classifying the kinase domains into subfamilies. The unusual domain combinations in particular kinases suggest their involvement in ubiquitination pathways and alternative modes of regulation for mitogen-activated protein kinase kinases (MAPKKs) and cyclin-dependent kinase (CDK)-like kinases. Previously unexplored kinases have been implicated in osteoblast differentiation and embryonic development on the basis of homology with kinases of known functions from other organisms. Kinases potentially unique to vertebrates are involved in highly evolved processes such as apoptosis, protein translation and tyrosine kinase signaling. In addition to coevolution with the kinase domain, duplication and recruitment of non-catalytic domains is apparent in signaling domains such as the PH, DAG-PE, SH2 and SH3 domains. Conclusions: Expansion of the functional repertoire and possible existence of alternative modes of regulation of certain kinases is suggested by their uncommon domain combinations. Experimental verification of the predicted implications of these kinases could enhance our understanding of their biological roles.

An improved Monte Carlo scheme for simulation of synthesis of nanoparticles in reverse micelles

An improved Monte Carlo technique is presented in this work to simulate nanoparticle formation through a micellar route. The technique builds on the simulation technique proposed by Bandyopadhyaya et al. (Langmuir 2000, 16, 7139) which is general and rigorous but at the same time very computation intensive, so much so that nanoparticle formation in low occupancy systems cannot be simulated in reasonable time. In view of this, several strategies, rationalized by simple mathematical analyses, are proposed to accelerate Monte Carlo simulations. These are elimination of infructuous events, removal of excess reactant postreaction, and use of smaller micelle population a large number of times. Infructuous events include collision of an empty micelle with another empty one or with another one containing only one molecule or only a solid particle. These strategies are incorporated in a new simulation technique which divides the entire micelle population in four classes and shifts micelles from one class to other as the simulation proceeds. The simulation results, throughly tested using chi-square and other tests, show that the predictions of the improved technique remain unchanged, but with more than an order of magnitude decrease in computational effort for some of the simulations reported in the literature. A post priori validation scheme for the correctness of the simulation results has been utilized to propose a new simulation strategy to arrive at converged simulation results with near minimum computational effort.

A Seven-Level Inverter Topology for Induction Motor Drive Using Two-Level Inverters and Floating Capacitor Fed H-Bridges

A multilevel inverter topology for seven-level space vector generation is proposed in this paper. In this topology, the seven-level structure is realized using two conventional two-level inverters and six capacitor-fed H-bridge cells. It needs only two isolated dc-voltage sources of voltage rating V(dc)/2 where V(dc) is the dc voltage magnitude required by the conventional neutral point clamped (NPC) seven-level topology. The proposed topology is capable of maintaining the H-bridge capacitor voltages at the required level of V(dc)/6 under all operating conditions, covering the entire linear modulation and overmodulation regions, by making use of the switching state redundancies. In the event of any switch failure in H-bridges, this inverter can operate in three-level mode, a feature that enhances the reliability of the drive system. The two-level inverters, which operate at a higher voltage level of V(dc)/2, switch less compared to the H-bridges, which operate at a lower voltage level of V(dc)/6, resulting in switching loss reduction. The experimental verification of the proposed topology is carried out for the entire modulation range, under steady state as well as transient conditions.

Method of Design Through Structuring of Meanings

This research shows a new approach and development of a design methodology, based on the perspective of meanings. In this study the design process is explored as a development of the structure of meanings. The processes of search and evaluation of meanings form the foundations of developing this structure. In order to facilitate the use and operation of the meanings, the WordNet lexical database and an existing visualization of WordNet — Visuwords — is used for the process of meaning search. The basic tool used for evaluation process is the WordNet::Similarity software, measuring the relatedness of meanings in the database. In this way it is measuring the degree of interconnections between different meanings. This kind of search and evaluation techniques are later on incorporated into our methodology of the structure of meanings to support the design process. The measures of relatedness of meanings are developed as convergence criteria for application in the processes of evaluation. Further on, the methodology for the structure of meanings developed here is used to construct meanings in a verification of product design. The steps of the design methodology, including the search and evaluation processes involved in developing the structure of the meanings, are elucidated. The choices, made by the designer in terms of meanings are supported by consequent searches and evaluations of meanings to be implemented in the designed product. In conclusion, the paper presents directions for developing and further extensions of the proposed design methodology.

Scalable Context-Sensitive Points-To Analysis Using Multi-Dimensional Bloom Filters

Context-sensitive points-to analysis is critical for several program optimizations. However, as the number of contexts grows exponentially, storage requirements for the analysis increase tremendously for large programs, making the analysis non-scalable. We propose a scalable flow-insensitive context-sensitive inclusion-based points-to analysis that uses a specially designed multi-dimensional bloom filter to store the points-to information. Two key observations motivate our proposal: (i) points-to information (between pointer-object and between pointer-pointer) is sparse, and (ii) moving from an exact to an approximate representation of points-to information only leads to reduced precision without affecting correctness of the (may-points-to) analysis. By using an approximate representation a multi-dimensional bloom filter can significantly reduce the memory requirements with a probabilistic bound on loss in precision. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that with an average storage requirement of 4MB, our approach achieves almost the same precision (98.6%) as the exact implementation. By increasing the average memory to 27MB, it achieves precision upto 99.7% for these benchmarks. Using Mod/Ref analysis as the client, we find that the client analysis is not affected that often even when there is some loss of precision in the points-to representation. We find that the NoModRef percentage is within 2% of the exact analysis while requiring 4MB (maximum 15MB) memory and less than 4 minutes on average for the points-to analysis. Another major advantage of our technique is that it allows to trade off precision for memory usage of the analysis.

A decidable temporal logic with repeating values

Various logical formalisms with the freeze quantifier have been recently considered to model computer systems even though this is a powerful mechanism that often leads to undecidability. In this paper, we study a linear-time temporal logic with past-time operators such that the freeze operator is only used to express that some value from an infinite set is repeated in the future or in the past. Such a restriction has been inspired by a recent work on spatio-temporal logics. We show decidability of finitary and infinitary satisfiability by reduction into the verification of temporal properties in Petri nets. This is a surprising result since the logic is closed under negation, contains future-time and past-time temporal operators and can express the nonce property and its negation. These ingredients are known to lead to undecidability with a more liberal use of the freeze quantifier.

Regenerative Dynamometer with Vector Controlled Drive

This paper presents the topology selection, design steps, simulation studies, design verification, system fabrication and performance evaluation on an induction motor based dynamometer system. The control algorithm used the application is well known field oriented control or vector control. Position sensorless scheme is adopted to eliminate the encoder requirement. The dynamometer is rated for 3.7kW. It can be used to determine the speed–torque characteristics of any rotating system. The rotating system is to be coupled with the vector controlled drive and the required torque command is given from the latter. The experimental verification is carried out for an open loop v/f drive as a test rotating system and important test results are presented.

Recovery from DoS Attacks in MIPv6: Modelling and Validation

Denial-of-service (DoS) attacks form a very important category of security threats that are prevalent in MIPv6 (mobile internet protocol version 6) today. Many schemes have been proposed to alleviate such threats, including one of our own [9]. However, reasoning about the correctness of such protocols is not trivial. In addition, new solutions to mitigate attacks may need to be deployed in the network on a frequent basis as and when attacks are detected, as it is practically impossible to anticipate all attacks and provide solutions in advance. This makes it necessary to validate the solutions in a timely manner before deployment in the real network. However, threshold schemes needed in group protocols make analysis complex. Model checking threshold-based group protocols that employ cryptography have not been successful so far. Here, we propose a new simulation based approach for validation using a tool called FRAMOGR that supports executable specification of group protocols that use cryptography. FRAMOGR allows one to specify attackers and track probability distributions of values or paths. We believe that infrastructure such as FRAMOGR would be required in future for validating new group based threshold protocols that may be needed for making MIPv6 more robust.

A unification-based decision procedure for cryptographic protocol analysis

We present a sound and complete decision procedure for the bounded process cryptographic protocol insecurity problem, based on the notion of normal proofs [2] and classical unification. We also show a result about the existence of attacks with “high” normal cuts. Our proof of correctness provides an alternate proof and new insights into the fundamental result of Rusinowitch and Turuani [9] for the same setting.

“Post silicon debug of SOC designs”

Continuous advances in VLSI technology have made implementation of very complicated systems possible. Modern System-on -Chips (SoCs) have many processors, IP cores and other functional units. As a result, complete verification of whole systems before implementation is becoming infeasible; hence it is likely that these systems may have some errors after manufacturing. This increases the need to find design errors in chips after fabrication. The main challenge for post-silicon debug is the observability of the internal signals. Post-silicon debug is the problem of determining what's wrong when the fabricated chip of a new design behaves incorrectly. This problem now consumes over half of the overall verification effort on large designs, and the problem is growing worse.Traditional post-silicon debug methods concentrate on functional parts of systems and provide mechanisms to increase the observability of internal state of systems. Those methods may not be sufficient as modern SoCs have lots of blocks (processors, IP cores, etc.) which are communicating with one another and communication is another source of design errors. This tutorial will be provide an insight into various observability enhancement techniques, on chip instrumentation techniques and use of high level models to support the debug process targeting both inside blocks and communication among them. It will also cover the use of formal methods to help debug process.

Spatio-temporal landscape modelling for natural hazard vulnerability analysis in select watersheds of Central Western Ghats

Natural hazards such as landslides are triggered by numerous factors such as ground movements, rock falls, slope failure, debris flows, slope instability, etc. Changes in slope stability happen due to human intervention, anthropogenic activities, change in soil structure, loss or absence of vegetation (changes in land cover), etc. Loss of vegetation happens when the forest is fragmented due to anthropogenic activities. Hence land cover mapping with forest fragmentation can provide vital information for visualising the regions that require immediate attention from slope stability aspects. The main objective of this paper is to understand the rate of change in forest landscape from 1973 to 2004 through multi-sensor remote sensing data analysis. The forest fragmentation index presented here is based on temporal land use information and forest fragmentation model, in which the forest pixels are classified as patch, transitional, edge, perforated, and interior, that give a measure of forest continuity. The analysis carried out for five prominent watersheds of Uttara Kannada district– Aganashini, Bedthi, Kali, Sharavathi and Venkatpura revealed that interior forest is continuously decreasing while patch, transitional, edge and perforated forest show increasing trend. The effect of forest fragmentation on landslide occurrence was visualised by overlaying the landslide occurrence points on classified image and forest fragmentation map. The increasing patch and transitional forest on hill slopes are the areas prone to landslides, evident from the field verification, indicating that deforestation is a major triggering factor for landslides. This emphasises the need for immediate conservation measures for sustainable management of the landscape. Quantifying and describing land use - land cover change and fragmentation is crucial for assessing the effect of land management policies and environmental protection decisions.

Flow from T-spout ladles

The ladle constitutes a crucial element in the pouring system for developing process consistency and quality in the manufacture of castings. Flow of molten metal from T-spout ladles, with the spout projecting at an angle from the shell of the ladle, was investigated by simulation, modeling and analysis. This was followed by experimental validation for water flow in translucent models, and verification in a cast iron foundry. Key parameters in the design of a ladle (for its geometry) have been identified as the ladle size, spout diameter and its angle. Velocity and flow rate from a T-spout ladle are governed by and increase with increase in angle of tilt apart from the aforementioned design parameters. Cross section and profile of the issuing jet displaying a stable twisting pattern, during its free-fall of model fluid water and molten metal iron, are notable aspects in the design of the ladle, particularly the spout exit.