Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

Designing fast LTL model checking algorithms for many-core GPUs

Recent technological developments made various many-core hardware platforms widely accessible. These massively parallel architectures have been used to significantly accelerate many computation demanding tasks. In this paper, we show how the algorithms for LTL model checking can be redesigned in order to accelerate LTL model checking on many-core GPU platforms. Our detailed experimental evaluation demonstrates that using the NVIDIA CUDA technology results in a significant speedup of the verification process. Together with state space generation based on shared hash-table and DFS exploration, our CUDA accelerated model checker is the fastest among state-of-the-art shared memory model checking tools.     

Renaming and the weakest family of failure detectors

We address the question of the weakest failure detector to circumvent the impossibility of $(2n-2)$ -renaming in a system of up to $n$ participating processes. We derive that in a restricted class of eventual failure detectors there does not exist a single weakest oracle, but a weakest family of oracles $\zeta _n$ : every two oracles in $\zeta _n$ are incomparable, and every oracle that allows for solving renaming provides at least as much information about failures as one of the oracles in $\zeta _n$ . As a by product, we obtain one more evidence that renaming is strictly easier to solve than set agreement.     

Automated synthesis of action selection policies for unmanned vehicles operating in adverse environments

We address the problem of automated action selection policy synthesis for unmanned vehicles operating in adverse environments. We introduce a new evolutionary computation-based approach using which an initial version of the policy is automatically generated and then gradually refined by detecting and fixing its shortcomings. The synthesis technique consists of the automated extraction of the vehicle’s exception states and Genetic Programming (GP) for automated composition and optimization of corrective sequences of commands in the form of macro-actions to be applied locally.     

Nonterminal complexity of one-sided random context grammars

In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen nonterminals in terms of these grammars with the set of left random context rules coinciding with the set of right random context rules. Furthermore, we introduce the notion of a right random context nonterminal, defined as a nonterminal that appears on the left-hand side of a right random context rule. We demonstrate how to convert any one-sided random context grammar G to an equivalent one-sided random context grammar H with two right random context nonterminals. An analogical conversion is given in terms of (1) propagating one-sided random context grammars and (2) left random context nonterminals. In the conclusion, two open problems are stated.     

Thermophysical Analysis of Sandstone by Pulse Transient Method

Stones belong to porous materials where water in pores plays an important role during the freeze–thaw process. A thermophysical analysis based on the pulse transient method has been used to study an ageing cycle, namely the freeze–thaw cycle. Thermophysical analysis is based on measuring the thermophysical properties under specific thermodynamic conditions. The transient method determines the specific heat, thermal diffusivity, and thermal conductivity by a single measurement. A specimen of Sander sandstone was analyzed in both dry and water-saturated states. Typical anomalies of all thermophysical parameters at the freeze–thaw point as well as differences for the dry and saturated states were found. The changes of thermophysical parameters measured when using freeze–thaw cycles correspond to stone ageing. The freeze–thaw cycle can often be encountered in building physics, concrete construction, etcPaper presented at the Seventh Asian Thermophysical Properties Conference, August 23–28, 2004, Hefei and Huangshan, Anhui, P. R. China.     

Study of structure and properties of ZnO–Bi<Subscript>2</Subscript>O<Subscript>3</Subscript>–P<Subscript>2</Subscript>O<Subscript>5</Subscript> glasses

Glasses of the ternary system ZnO–Bi₂O₃–P₂O₅ were prepared and studied in two compositional series 50ZnO–xBi₂O₃–(50 − x)P₂O₅ and (50 − y)ZnO–yBi₂O₃–50P₂O₅. Two distinct glass-forming regions were found in the 50ZnO–xBi₂O₃–(50 − x)P₂O₅ glass series with x = 0–10 and 20–35 mol.% Bi₂O₃. All prepared Bi₂O₃-containing glasses reveal a high chemical durability. Small additions of Bi₂O₃ (∼5 mol.%) improve thermal stability of glasses. All glasses crystallize on heating within the temperature range of 505–583 °C. Structural studies by Raman and ³¹P MAS NMR spectroscopies showed the rapid depolymerisation of phosphate chains within the first region with x = 0–15 and the presence of isolated Q⁰ phosphate units within the second region with x = 20–35. Raman studies showed that bismuth is incorporated in the glass structure in BiO₆ units and their vibrational bands were observed within the spectral region of 350–700 cm⁻¹. The evolution of properties and the spectroscopic data are both in accordance with a network former effect of Bi₂O₃.     

Contact Doping for Vertical Organic Field‐Effect Transistors

Doping is a powerful tool to overcome contact limitations in short‐channel organic field‐effect transistors (OFETs) and has been successfully used in the past to improve the charge carrier injection in OFETs. The present study applies this familiar concept to the architecture of vertical organic field‐effect transistors (VOFETs), which are often severely limited by injection due to their very short channel lengths. The present study shows that the performance of p‐type VOFETs with pentacene as an active material can be significantly enhanced by the addition of the common p‐dopant C₆₀F₃₆ as a thin injection layer underneath the VOFET source electrode, resulting in an increase of On‐state current and On/Off ratio by one order of magnitude. The present study further investigates mixed injection layers of pentacene and the p‐dopant and finds that the improvement is less pronounced than for the pure dopant layers and depends on the concentration of dopant molecules in the injection layer. Through application of the transfer length method to equivalent OFET geometries, the present study is finally able to link the observed improvement to a decrease in transfer length and can thus conclude that this length is a crucial parameter onto which further improvement efforts have to be concentrated to realize true short‐channel VOFETs.     

Color Cherenkov imaging of clinical radiation therapy

Color vision is used throughout medicine to interpret the health and status of tissue. Ionizing radiation used in radiation therapy produces broadband white lig...     

Efficient Geodesic Attribute Thinnings Based on the Barycentric Diameter

An attribute opening is an idempotent, anti-extensive and increasing operator, which removes from an image connected components which do not fulfil a given criterion. When the increasingness property is dropped, we obtain a—more general—attribute thinning. In this paper, we propose efficient grey scale thinnings based on geodesic attributes. Given that the geodesic diameter is time consuming, we propose a new geodesic attribute, the barycentric diameter to speed up the computation time. Then, we give the theoretical error bound between these two attributes, and we note that in practice, the barycentric diameter gives very similar results in comparison with the geodesic diameter. Finally, we present the algorithm with further optimisations, to obtain a 60× speed up. We illustrate the use of these thinnings in automated non-destructive material inspection: the detection of cracks. We discuss the advantages of these operators over other methods such as path openings or the supremum of openings with segments.