Convex combinations of strict t-norms

Alsina, Frank, and Schweizer posed a question whether a non-trivial convex combination of triangular norms can ever be a triangular norm. In this paper we deal with the class of strict t-norms with well-defined first partial derivatives along their zero borders. We show that the answer to the question is negative for certain couples of such t-norms and we state out possible further research.     

Estimation of time-dependent input from neuronal membrane potential

The set of firing rates of the presynaptic excitatory and inhibitory neurons constitutes the input signal to the postsynaptic neuron. Estimation of the time-varying input rates from intracellularly recorded membrane potential is investigated here. For that purpose, the membrane potential dynamics must be specified. We consider the Ornstein-Uhlenbeck stochastic process, one of the most common single-neuron models, with time-dependent mean and variance. Assuming the slow variation of these two moments, it is possible to formulate the estimation problem by using a state-space model. We develop an algorithm that estimates the paths of the mean and variance of the input current by using the empirical Bayes approach. Then the input firing rates are directly available from the moments. The proposed method is applied to three simulated data examples: constant signal, sinusoidally modulated signal, and constant signal with a jump. For the constant signal, the estimation performance of the method is comparable to that of the traditionally applied maximum likelihood method. Further, the proposed method accurately estimates both continuous and discontinuous time-variable signals. In the case of the signal with a jump, which does not satisfy the assumption of slow variability, the robustness of the method is verified. It can be concluded that the method provides reliable estimates of the total input firing rates, which are not experimentally measurable.     

The joint movement of pebbles in solving the ($$N^2-1$$)-puzzle suboptimally and its applications in rule-based cooperative path-finding

The present paper deals with the problem of solving the (\(n^2 - 1\))-puzzle and cooperative path-finding (CPF) problems sub-optimally by rule-based algorithms. To solve the puzzle, we need to rearrange \(n^2 - 1\) pebbles in the \(n \times n\)-sized square grid using one vacant position to achieve the goal configuration. An improvement to the existing polynomial-time algorithm is proposed and experimentally analyzed. The improved algorithm represents an attempt to move pebbles in a more efficient way compared to the original algorithm by grouping them into so-called snakes and moving them together as part of a snake formation. An experimental evaluation has shown that the snakeenhanced algorithm produces solutions which are 8–9 % shorter than the solutions generated by the original algorithm. Snake-like movement has also been integrated into the rule-based algorithms used in solving CPF problems sub-optimally, which is a closely related task. The task in CPF consists in moving a group of abstract robots on an undirected graph to specific vertices. The robots can move to unoccupied neighboring vertices; no more than one robot can be placed in each vertex. The (\(n^2 - 1\))-puzzle is a special case of CPF where the underlying graph is a 4-connected grid and only one vertex is vacant. Two major rule-based algorithms for solving CPF problems were included in our study—BIBOX and PUSH-and-SWAP (PUSH-and-ROTATE). The use of snakes in the BIBOX algorithm led to consistent efficiency gains of around 30 % for the (\(n^2 - 1\))-puzzle and up to 50 % in for CPF problems on biconnected graphs with various ear decompositions and multiple vacant vertices. For the PUSH-and-SWAP algorithm, the efficiency gain achieved from the use of snakes was around 5–8 %. However, the efficiency gain was unstable and hardly predictable for PUSH-and-SWAP.     

Using meta‐modeling in design and implementation of component‐based systems: the SOFA case study

To allow efficient and user‐friendly development of a component‐based application, component systems have to provide a rather complex development infrastructure, including a tool for component composition, component repository, and a run‐time infrastructure. In this paper, we present and evaluate benefits of using meta‐modeling during the process of defining a component system and also during creation of the development and run‐time infrastructures. Most of the presented arguments are based on a broad practical experience with designing the component systems SOFA and SOFA 2; the former designed in a classical ad hoc ‘manual’ way, whereas the latter with the help of meta‐modeling. Copyright © 2010 John Wiley & Sons, Ltd.     

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.