On regular temporal logics with past

The IEEE standardized Property Specification Language, PSL for short, extends the well-known linear-time temporal logic LTL with so-called semi-extended regular expressions. PSL and the closely related SystemVerilog Assertions, SVA for short, are increasingly used in many phases of the hardware design cycle, from specification to verification. In this article, we extend the common core of these specification languages with past operators. We name this extension PPSL. Although all ω-regular properties are expressible in PSL, SVA, and PPSL, past operators often allow one to specify properties more naturally and concisely. In fact, we show that PPSL is exponentially more succinct than the cores of PSL and SVA. On the star-free properties, PPSL is double exponentially more succinct than LTL. Furthermore, we present a translation of PPSL into language-equivalent nondeterministic Büchi automata, which is based on novel constructions for 2-way alternating automata. The upper bound on the size of the resulting nondeterministic Büchi automata obtained by our translation is almost the same as the upper bound for the nondeterministic Büchi automata obtained from existing translations for PSL and SVA. Consequently, the satisfiability problem and the model-checking problem for PPSL fall into the same complexity classes as the corresponding problems for PSL and SVA.     

Soil moisture estimation over vegetated terrains using multitemporal remote sensing data

A new method for retrieving soil moisture content over vegetated fields, employing multitemporal radar and optical images, is presented. It is based on the integration of the temporal series of radar data within an inversion scheme and on the correction of the vegetation effects. The retrieval algorithm uses the Bayesian maximum posterior probability and assumes the existence of a relation among the soil conditions at the different times of the series. The correction of the vegetation effects models the variation, with respect to the initial time of the series, of the component of the backscattering coefficient due to the soil characteristics as function of the variations of the measured backscattering coefficient and of the biomass. The method is tested on the data acquired throughout the SMEX02 experiment. The results show that measured and estimated soil moistures are fairly well correlated and that the performances of multitemporal retrieval algorithm are better than those obtained by employing one radar acquisition, especially in terms of capability to detect soil moisture changes. Although the approach to correct the vegetation effects on radar observations needs to be further assessed on different sets of data, this finding demonstrates that the proposed method has a potential to improve the quality of the soil moisture retrievals.     

Tight analysis of the (1+1)-EA for the single source shortest path problem

We conduct a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld, and Wegener (The analyses of evolutionary algorithms on sorting and shortest paths problems, 2004, Journal of Mathematical Modelling and Algorithms, 3(4):349-366). We prove that with high probability, the optimization time is O(n2 max{?, log(n)}), where ? is the smallest integer such that any vertex can be reached from the source via a shortest path having at most ? edges. This bound is tight. For all values of n and ? we provide a graph with edge weights such that, with high probability, the optimization time is of order Ω(n2 max{?, log(n)}). To obtain such sharp bounds, we develop a new technique that overcomes the coupon collector behavior of previously used arguments. Also, we exhibit a simple Chernoff type inequality for sums of independent geometrically distributed random variables, and one for sequences of random variables that are not independent, but show a desired behavior independent of the outcomes of the previous random variables. We are optimistic that these tools find further applications in the analysis of evolutionary algorithms.     

GPU-based real-time approximation of the ablation zone for radiofrequency ablation

Percutaneous radiofrequency ablation (RFA) is becoming a standard minimally invasive clinical procedure for the treatment of liver tumors. However, planning the applicator placement such that the malignant tissue is completely destroyed, is a demanding task that requires considerable experience. In this work, we present a fast GPU-based real-time approximation of the ablation zone incorporating the cooling effect of liver vessels. Weighted distance fields of varying RF applicator types are derived from complex numerical simulations to allow a fast estimation of the ablation zone. Furthermore, the heat-sink effect of the cooling blood flow close to the applicator's electrode is estimated by means of a preprocessed thermal equilibrium representation of the liver parenchyma and blood vessels. Utilizing the graphics card, the weighted distance field incorporating the cooling blood flow is calculated using a modular shader framework, which facilitates the real-time visualization of the ablation zone in projected slice views and in volume rendering. The proposed methods are integrated in our software assistant prototype for planning RFA therapy. The software allows the physician to interactively place virtual RF applicator models. The real-time visualization of the corresponding approximated ablation zone facilitates interactive evaluation of the tumor coverage in order to optimize the applicator's placement such that all cancer cells are destroyed by the ablation.     

Distance visualization for interactive 3D implant planning

An instant and quantitative assessment of spatial distances between two objects plays an important role in interactive applications such as virtual model assembly, medical operation planning, or computational steering. While some research has been done on the development of distance-based measures between two objects, only very few attempts have been reported to visualize such measures in interactive scenarios. In this paper we present two different approaches for this purpose, and we investigate the effectiveness of these approaches for intuitive 3D implant positioning in a medical operation planning system. The first approach uses cylindrical glyphs to depict distances, which smoothly adapt their shape and color to changing distances when the objects are moved. This approach computes distances directly on the polygonal object representations by means of ray/triangle mesh intersection. The second approach introduces a set of slices as additional geometric structures, and uses color coding on surfaces to indicate distances. This approach obtains distances from a precomputed distance field of each object. The major findings of the performed user study indicate that a visualization that can facilitate an instant and quantitative analysis of distances between two objects in interactive 3D scenarios is demanding, yet can be achieved by including additional monocular cues into the visualization.     

Numerical investigation of cyclic variations in gasoline engines using a hybrid URANS/LES modeling approach

Cycle to cycle variations are an important aspect in the development and optimization process of internal combustion engines. In this study the feasibility of using a detached eddy simulation (DES) SST model, which is a hybrid URANS/LES model, to predict cycle to cycle variations is investigated. In the near wall region or in regions where the grid resolution is not sufficiently fine to resolve smaller structures, the two-equation RANS shear-stress transport (SST) model is used. In the other regions with higher grid resolution an LES model is applied. First, the numerical requirements associated with the hybrid URANS/LES and the employed solver are studied in detail. The numerical dissipation of the spatial scheme and the choice of the temporal scheme including the step size are evaluated. In addition, the accuracy of the solver for moving meshes, which are required for engine calculations, is assessed. The modeling constant linking the grid size to the DES filter length scale is determined by calculating a decaying homogeneous isotropic turbulence test case for different grid resolutions. The final applications of the model are two different engine cases with increasing complexity. The first case is the statistically stationary flow through an engine intake port. The time resolved flow structure predicted by the DES SST model is analyzed and the resulting time-averaged velocity fields are compared to experimental data at different locations. The second application is a motored multi-cycle simulation of a series production engine. The instantaneous flow development during the intake and compression stroke of one single cycle is studied and the ensemble-averaged and the instantaneous velocity fields as well as the resolved velocity fluctuations are compared to optical measurements. Special emphasis is placed on the cyclic differences of the velocity fluctuations at the time of ignition in the vicinity of the spark plug and the expected influence on the combustion process.     

An algebraic foundation for automatic feature-based program synthesis

Feature-Oriented Software Development provides a multitude of formalisms, methods, languages, and tools for building variable, customizable, and extensible software. Along different lines of research, different notions of a feature have been developed. Although these notions have similar goals, no common basis for evaluation, comparison, and integration exists. We present a feature algebra that captures the key ideas of feature orientation and that provides a common ground for current and future research in this field, on which also alternative options can be explored. Furthermore, our algebraic framework is meant to serve as a basis for the development of the technology of automatic feature-based program synthesis and architectural metaprogramming.