Inference of message sequence charts

Software designers draw message sequence charts for early modeling of the individual behaviors they expect from the concurrent system under design. Can they be sure that precisely the behaviors they have described are realizable by some implementation of the components of the concurrent system? If so, can we automatically synthesize concurrent state machines realizing the given MSCs? If, on the other hand, other unspecified and possibly unwanted scenarios are "implied" by their MSCs, can the software designer be automatically warned and provided the implied MSCs? In this paper, we provide a framework in which all these questions are answered positively. We first describe the formal framework within which one can derive implied MSCs and then provide polynomial-time algorithms for implication, realizability, and synthesis.     

An Until Hierarchy and Other Applications of an Ehrenfeucht–Fraïssé Game for Temporal Logic

We prove there is a strict hierarchy of expressive power according to the Until depth of linear temporal logic (LTL) formulas: for each k, there is a natural property, based on quantitative fairness, that is not expressible with k nestings of Until operators, regardless of the number of applications of other operators, but is expressible by a formula with Until depth k+1. Our proof uses a new Ehrenfeucht–Fraïssé (EF) game designed specifically for LTL. These properties can all be expressed in first-order logic with quantifier depth and size (log k), and we use them to observe some interesting relationships between LTL and first-order expressibility. We note that our Until hierarchy proof for LTL carries over to the branching time logics, CTL and CTL*. We then use the EF game in a novel way to effectively characterize (1) the LTL properties expressible without Until, as well as (2) those expressible without both Until and Next. By playing the game “on finite automata,” we prove that the automata recognizing languages expressible in each of the two fragments have distinctive structural properties. The characterization for the first fragment was originally proved by Cohen, Perrin, and Pin using sophisticated semigroup-theoretic techniques. They asked whether such a characterization exists for the second fragment. The technique we develop is general and can potentially be applied in other contexts.     

First-Order Logic with Two Variables and Unary Temporal Logic

We investigate the power of first-order logic with only two variables over ω-words and finite words, a logic denoted by FO². We prove that FO² can express precisely the same properties as linear temporal logic with only the unary temporal operators: “next,” “previously,” “sometime in the future,” and “sometime in the past,” a logic we denote by unary-TL Moreover, our translation from FO² to unary-TL converts every FO² formula to an equivalent unary-TL formula that is at most exponentially larger and whose operator depth is at most twice the quantifier depth of the first-order formula. We show that this translation is essentially optimal. While satisfiability for full linear temporal logic, as well as for unary-TL, is known to be PSPACE-complete, we prove that satisfiability for FO² is NEXP-complete, in sharp contrast to the fact that satisfiability for FO³ has nonelementary computational complexity. Our NEXP upper bound for FO² satisfiability has the advantage of being in terms of the quantifier depth of the input formula. It is obtained using a small model property for FO² of independent interest, namely, a satisfiable FO² formula has a model whose size is at most exponential in the quantifier depth of the formula. Using our translation from FO² to unary-TL we derive this small model property from a corresponding small model property for unary-TL. Our proof of the small model property for unary-TL is based on an analysis of unary-TL types.     

Nanostructure of Er3+ doped silicates

We demonstrate nanostructural evolution resulting in highly increased photoluminescence in silicates doped with Er3+ ions. High-resolution transmission electron microscopy (HRTEM) imaging, nano-energy dispersed X-ray (NEDX) spectroscopy, X-ray diffraction (XRD) and photoluminescence analysis confirm the local composition and structure changes of the Er3+ ions upon thermal annealing. We studied two types of amorphous nanopowder: the first is of the composition SiO2/18Al2O3/2Er2O3 (SAE), synthesized by combustion flame-chemical vapor condensation, and the second is with a composition of SiO2/8Y2O3/2Er2O3 (SYE), synthesized by sol-gel synthesis (composition in mol%). Electron diffraction and HRTEM imaging clearly show the formation of nanocrystallites with an average diameter of approximately 8 nm in SAE samples annealed at 1000 degrees C and SYE samples annealed at 1200 degrees C. The volume fraction of the nanocrystalline phase increased with each heat treatment, eventually leading to complete devitrification at 1400 degrees C. Further XRD and NEDX analysis indicates that the nanocrystalline phase has the pyrochlore structure with the formula Er(x)Al(2-x)Si2O7 or Er(x)Y(2-x)Si2O7 and a surrounding silica matrix.