Context-sensitive refinements for stochastic optimisation algorithms in inductive logic programming

We describe a new approach to the application of stochastic search in Inductive Logic Programming (ILP). Unlike traditional approaches we do not focus directly on evolving logical concepts but our refinement-based approach uses the stochastic optimization process to iteratively adapt the initial working concept. Utilization of context-sensitive concept refinements (adaptations) helps the search operations to produce mostly syntactically correct concepts. It also enables using available background knowledge both for efficiently restricting the search space and for directing the search. Thereby, the search is more flexible, less problem-specific and the framework can be easily used with any stochastic search algorithm within ILP domain. Experimental results on several data sets verify the usefulness of this approach.     

Parameterized complexity of coloring problems: Treewidth versus vertex cover

We compare the fixed parameter complexity of various variants of coloring problems (including List Coloring, Precoloring Extension, Equitable Coloring, L(p,1)-Labeling and Channel Assignment) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems.     

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.     

Linear color segmentation and its implementation

A framework for color image segmentation is presented, which combines color histogram analysis and region merging approach. Its main goal is to segment an image at material boundaries (i.e., discontinuities of reflectance properties) while ignoring spatial color inhomogeneities of uniformly pigmented (colored) objects, caused by accidents of illumination and viewing geometry. Theoretical examination of light spectrum transformations upon light reflection from material surfaces and upon interaction with a sensor system shows that in a wide variety of viewed scenes (even containing interreflections and highlight areas) uniformly pigmented objects are projected to the color space of the sensor as planar, linear, or point-like clusters, depending on lighting and viewing conditions and object geometry. To detect such clusters in the color space, three methods are suggested: Generalized Hough Transform method, gradient descent method, and eigenvectors method. A framework algorithm of color segmentation based on region merging approach is developed, which can use any of these methods. Testing this algorithm with both artificially generated and real images shows quite reliable results.     

Analysis of time-domain and spectral-domain two-beam interference including the effect of a variable spectral bandpass of a detecting system

Abstract

The effect of a variable Gaussian response function of a monochromator in a detecting system with a broadband detector is included in the theoretical and experimental analysis of time-domain and spectral-domain interference of two light beams from a source of a multimode Gaussian spectrum. The time-domain theoretical analysis gives the analytic expressions for the measured complex degree of temporal coherence of the light with and without the effect of variable spectral bandpass of the detecting system. The spectral-domain theoretical analysis of the two-beam interference gives the spectral interference law from which the visibility of the spectral interference fringes resolved for a given delay in the interferometer by a spectrometer is expressed as a function of the bandpass of the spectrometer. The theoretical conclusions are confirmed experimentally in the Michelson interferometer configuration using a laser diode operated below the threshold, a prism monochromator and a p-i-n photodetector. From the width of the central peak in the measured visibility dependence that narrows with increasing slit width of the monochromator, the spectral bandpass of the monochromator is evaluated. It is also shown how the visibility of the spectral interference fringes decreases as the slit width of the prism spectrometer increases.