In-Situ and Real-Time Investigation of Columnar-to-Equiaxed Transition in Metallic Alloy

In this article, we present a review of observations during Al-3.5 wt pct Ni alloy solidi.cation experiments performed at the European Synchrotron Radiation Facility (ESRF) in Grenoble. These experiments provide direct access to dynamical phenomena during columnar growth (initial transient and breakdown of a planar solid-liquid interface), and for the first time to the transition from columnar-to-equiaxed microstructure (nucleation ahead of a columnar front and blocking of a columnar front by an equiaxed microstructure) and fully equiaxed growth (propagation of an effective front). Based on these experimental observations, critical parameters such as columnar growth velocity variation during the transition or equiaxed-grain diameter are measured and discussed. This article is based on a presentation made in the symposium entitled “Solidi.cation Modeling and Microstructure Formation: In Honor of Prof. John Hunt,” which occurred March 13–15, 2006, during the TMS Spring Meeting in San Antonio, Texas, under the auspices of the TMS Materials Processing and Manufacturing Division, Solidification Committee.     

Finding Induced Paths of Given Parity in Claw-Free Graphs

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time.     

Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks

In project management, three quantities are often used by project managers: the earliest starting date, the latest starting date and the float of tasks. These quantities are computed by the Program Evaluation and Review Techniques/Critical Path Method (PERT/CPM) algorithm. When task durations are ill known, as is often the case at the beginning of a project, they can be modeled by means of intervals, representing the possible values of these task durations. With such a representation, the earliest starting dates, the latest starting dates and the floats are also intervals. The purpose of this paper is to give efficient algorithms for their computation. After recalling the classical PERT/CPM problem, we present several properties of the concerned quantities in the interval-valued case, showing that the standard criticality analysis collapses. We propose an efficient algorithm based on path enumeration to compute optimal intervals for latest starting times and floats in the general case, and a simpler polynomial algorithm in the case of series-parallel activity networks.     

Concurrent software verification with states, events, and deadlocks

We present a framework for model checking concurrent software systems which incorporates both states and events. Contrary to other state/event approaches, our work also integrates two powerful verification techniques, counterexample-guided abstraction refinement and compositional reasoning. Our specification language is a state/event extension of linear temporal logic, and allows us to express many properties of software in a concise and intuitive manner. We show how standard automata-theoretic LTL model checking algorithms can be ported to our framework at no extra cost, enabling us to directly benefit from the large body of research on efficient LTL verification. We also present an algorithm to detect deadlocks in concurrent message-passing programs. Deadlock- freedom is not only an important and desirable property in its own right, but is also a prerequisite for the soundness of our model checking algorithm. Even though deadlock is inherently non-compositional and is not preserved by classical abstractions, our iterative algorithm employs both (non-standard) abstractions and compositional reasoning to alleviate the state-space explosion problem. The resulting framework differs in key respects from other instances of the counterexample-guided abstraction refinement paradigm found in the literature. We have implemented this work in the magic verification tool for concurrent C programs and performed tests on a broad set of benchmarks. Our experiments show that this new approach not only eases the writing of specifications, but also yields important gains both in space and in time during verification. In certain cases, we even encountered specifications that could not be verified using traditional pure event-based or state-based approaches, but became tractable within our state/event framework. We also recorded substantial reductions in time and memory consumption when performing deadlock-freedom checks with our new abstractions. Finally, we report two bugs (including a deadlock) in the source code of Micro-C/OS versions 2.0 and 2.7, which we discovered during our experiments. This research was sponsored by the National Science Foundation (NSF) under grants no. CCR-9803774 and CCR-0121547, the Office of Naval Research (ONR) and the Naval Research Laboratory (NRL) under contract no. N00014-01-1-0796, the Army Research Office (ARO) under contract no. DAAD19-01-1-0485, and was conducted as part of the Predictable Assembly from Certifiable Components (PACC) project at the Software Engineering Institute (SEI). This article combines and builds upon the papers (CCO⁺04) and (CCOS04). Received December 2004 Revised July 2005 Accepted July 2005 by Eerke A. Boiten, John Derrick, Graeme Smith and Ian Hayes     

An Application of an Initialization Protocol to Permutation Routing in a Single-Hop Mobile Ad Hoc Networks

In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in broadcast rounds if k p and if each station has a -memory locations. And if k and if each station has a -memory locations, the permutations of these n pretitled items can be done also in broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of stations. Finally we show that the permutation routing problem can be solved on it in broadcast rounds in the worst case. It can be solved in broadcast rounds in the better case. Note that our approach does not impose any restriction on k.     

A geosemantic proximity-based prototype for the interoperability of geospatial data

The research agenda related to the interoperability of geospatial data is influenced by the increased accessibility of geospatial databases on the Internet, as well as their sharing and their integration. Although it is now possible to get and use geospatial data independently of their syntax and structure, it is still difficult for users to find the exact data they need as long as they do not know the precise vocabulary used by the organizations supporting geospatial databases. It is now a necessity to take into consideration the semantics of geospatial data to enable its full interoperability.To this end, we designed a new conceptual framework for geospatial data interoperability and introduced the notion of geosemantic proximity based on human communication and cognition paradigms. This paper reviews this framework and the notion of geosemantic proximity. It also presents the GsP Prototype, which demonstrates the relevance of our framework and of the notion of geosemantic proximity for geospatial data interoperability. More specifically, we describe the architecture of the GsP Prototype, its implementation, and tests that have been conducted.     

Abstraction and resolution modulo AC: How to verify Diffie–Hellman-like protocols automatically

We show how cryptographic protocols using Diffie–Hellman primitives, i.e., modular exponentiation on a fixed generator, can be encoded in Horn clauses modulo associativity and commutativity. In order to obtain a sufficient criterion of security, we design a complete (but not sound in general) resolution procedure for a class of flattened clauses modulo simple equational theories, including associativity–commutativity. We report on a practical implementation of this algorithm in the MOP modular platform for automated proving; in particular, we obtain the first fully automated proof of security of the IKA.1 initial key agreement protocol in the so-called pure eavesdropper model.     

The semantics of augmented constraint diagrams

Constraint diagrams are a diagrammatic notation which may be used to express logical constraints. They generalize Venn diagrams and Euler circles, and include syntax for quantification and navigation of relations. The notation was designed to complement the Unified Modelling Language in the development of software systems.Since symbols representing quantification in a diagrammatic language can be naturally ordered in multiple ways, some constraint diagrams have more than one intuitive meaning in first-order predicate logic. Any equally expressive notation which is based on Euler diagrams and conveys logical statements using explicit quantification will have to address this problem.We explicitly augment constraint diagrams with reading trees, which provides a partial ordering for the quantifiers (determining their scope as well as their relative ordering). Alternative approaches using spatial arrangements of components, or alphabetical ordering of symbols, for example, can be seen as implicit representations of a reading tree.Whether the reading tree accompanies the diagram explicitly (optimizing expressiveness) or implicitly (simplifying diagram syntax), we show how to construct unambiguous semantics for the augmented constraint diagram.     

Effects of antagonistic co-contraction on differences between electromyography based and optimization based estimates of spinal forces

Estimates of spinal forces are quite sensitive to model assumptions, especially regarding antagonistic co-contraction. Optimization based models predict co-contraction to be absent, while electromyography (EMG) based models take co-contraction into account, but usually assume equal activation of deep and superficial parts of a muscle. The aim of the present study was to compare EMG based and optimization based estimates of spinal forces in a wide range of work tasks. Data obtained from ten subjects performing a total of 28 tasks were analysed with an EMG driven model and three optimization models, which were specifically designed to test the effects of the above assumptions. Estimates of peak spinal forces obtained using the different modelling approaches were similar for total muscle force and its compression component (on average EMG based predictions were 5% higher) and were closely related (R > 0.92), while differences in predictions of the peak shear component of muscle force were more substantial (with up to 39% lower estimates in optimization based models, R > 0.79). The results show that neither neglecting antagonistic co-contraction, nor assuming equal activation of deep and superficial muscles, has a major effect on estimates of spinal forces. The disparity between shear force predictions was due to an overestimation of activity of the lateral part of the internal oblique muscle by the optimization models, which is explained by the cost function preferentially recruiting larger muscles. This suggests that a penalty for active muscle mass should be included in the cost function used for predicting trunk muscle recruitment.     

Self-emergence of a common lexicon by evolution in teams of autonomous agents

In multi-agent systems, the study of language and communication is an active field of research. In this paper we present the application of evolutionary strategies to the self-emergence of a common lexicon in a population of agents. By modeling the vocabulary or lexicon of each agent as an association matrix or look-up table that maps the meanings (i.e. the objects encountered by the agents or the states of the environment itself) into symbols or signals we check whether it is possible for the population to converge in an autonomous, decentralized way to a common lexicon, so that the communication efficiency of the entire population is optimal. We have conducted several experiments aimed at testing whether it is possible to converge with evolutionary strategies to an optimal Saussurean communication system. We have organized our experiments alongside two main lines: first, we have investigated the effect of the population size on the convergence results. Second, and foremost, we have also investigated the effect of the lexicon size on the convergence results. To analyze the convergence of the population of agents we have defined the population's consensus when all the agents (i.e. 100% of the population) share the same association matrix or lexicon. As a general conclusion we have shown that evolutionary strategies are powerful enough optimizers to guarantee the convergence to lexicon consensus in a population of autonomous agents.