Realizability and verification of MSC graphs

Scenario-based specifications such as message sequence charts (MSC) offer an intuitive and visual way to describe design requirements. MSC-graphs allow convenient expression of multiple scenarios, and can be viewed as an early model of the system that can be subjected to a variety of analyses. Problems such as LTL model checking are undecidable for MSC-graphs in general, but are known to be decidable for the class of bounded MSC-graphs.Our first set of results concerns checking realizability of bounded MSC-graphs. An MSC-graph is realizable if there is a distributed implementation that generates precisely the behaviors in the graph. There are two notions of realizability, weak and safe, depending on whether or not we require the implementation to be deadlock-free. It is known that for a finite set of MSCs, weak realizability is coNP-complete while safe realizability has a polynomial-time solution. We establish that for bounded MSC-graphs, weak realizability is, surprisingly, undecidable, while safe realizability is in EXPSPACE.Our second set of results concerns verification of MSC-graphs. While checking properties of a graph $G$, besides verifying all the scenarios in the set $L(G)$ of MSCs specified by $G$, it is desirable to verify all the scenarios in the set $L^w(G)$—the closure of $G$, that contains the implied scenarios that any distributed implementation of $G$ must include. For checking whether a given MSC $M$ is a possible behavior, checking $M\in L(G)$ is NP-complete, but checking $M\in L^w(G)$ has a quadratic solution. For temporal logic specifications, considering the closure makes the verification problem harder: while checking LTL properties of $L(G)$ is PSPACE-complete for bounded graphs $G$, checking even simple “local” properties of $L^w(G)$ is undecidable.     

A thermodynamic assessment of the Co–Sn system

A critical evaluation and thermodynamic modeling of the phase diagram and thermodynamic properties have been presented for the Co–Sn system. More attention has been paid to reproduce the thermodynamic properties of the liquid Co–Sn, including the appreciable temperature dependence in the mixing enthalpy and the sign-variable activity with composition observed by experiments. A four-sublattice model has been used to describe the ordering phenomenon between $\beta {\mathrm{Co}}_3{\mathrm{Sn}}_2$ and $\alpha {\mathrm{Co}}_3{\mathrm{Sn}}_2$.     

Spectral-element discontinuous Galerkin lattice Boltzmann simulation of flow past two cylinders in tandem with an exponential time integrator

In this paper, a spectral-element discontinuous Galerkin (SEDG) lattice Boltzmann discretization and an exponential time-marching scheme are used to study the flow field past two circular cylinders in tandem arrangement. The basic idea is to discretize the streaming step of the lattice Boltzmann equation by using the SEDG method to get a system of ordinary differential equations (ODEs) whose exact solutions are expressed by using a large matrix exponential. The approximate solution of the resulting ODEs are obtained from a projection method based on a Krylov subspace approximation. This approach allows us to approximate the matrix exponential of a very large and sparse matrix by using a matrix of much smaller dimension. The exponential time integration scheme is useful especially when computations are carried out at high Courant–Friedrichs–Lewy ($CFL$) numbers, where most explicit time-marching schemes are inaccurate. Simulations of flow were carried out for a circular cylinder at $Re=20$ and for two circular cylinders in tandem at $Re=40$ and a spacing of $2.5D$, where $D$ is the diameter of the cylinders. We compare our results with those from a fourth-order Runge–Kutta scheme that is restricted by the $CFL$ number. In addition, important flow parameters such as the drag coefficients of the two cylinders and the wake length behind the rear cylinder were calculated by using the exponential time integration scheme. These results are compared with results from our simulation using the RK scheme and with existing benchmark results.     

Intersection-types à la Church

In this paper, we present ${\mathrm{\Lambda }}_{\wedge }^{\text{t}}$, a fully typed λ-calculus based on the intersection-type system discipline, which is a counterpart à la Church of the type assignment system as invented by Coppo and Dezani. The relationship between ${\mathrm{\Lambda }}_{\wedge }^{\text{t}}$ and the intersection type assignment system is the standard isomorphism between typed and type assignment system, and so the typed language inherits from the untyped system all the good properties, like subject reduction and strong normalization. Moreover, both type checking and type reconstruction are decidable.