-regular languages defined by a limit operator.
1.0957-Approximation Algorithm for Random MAX-3SAT
We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.
2-layer straightline crossing minimization: Performance of exact and heuristic algorithms.
minus the .
4D Embryogenesis image analysis using PDE methods of image processing
In this paper, we introduce a set of methods for processing and analyzing long time series of 3D images representing embryo evolution. The images are obtained by in vivo scanning using a confocal microscope where one of the channels represents the cell nuclei and the other one the cell membranes. Our image processing chain consists of three steps: image filtering, object counting (center detection) and segmentation. The corresponding methods are based on numerical solution of nonlinear PDEs, namely...
5-abelian cubes are avoidable on binary alphabets
A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.
-пространства.
9th Asian Logic Conference, Novosibirsk, Russia, 16--19 August 2005.
A backward selection procedure for approximating a discrete probability distribution by decomposable models
Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution over a finite set of discrete variables and a positive integer , find a decomposable model with tree-width that best fits . If is the generating hypergraph of a decomposable model and is the estimate of under the model, we can measure...
A belief revision approach for argumentation-based negotiation agents
Negotiation is an interaction that happens in multi-agent systems when agents have conflicting objectives and must look for an acceptable agreement. A typical negotiating situation involves two agents that cannot reach their goals by themselves because they do not have some resources they need or they do not know how to use them to reach their goals. Therefore, they must start a negotiation dialogue, taking also into account that they might have incomplete or wrong beliefs about the other agent's...
A Bimodality Test in High Dimensions
We present a test for identifying clusters in high dimensional data based on the k-means algorithm when the null hypothesis is spherical normal. We show that projection techniques used for evaluating validity of clusters may be misleading for such data. In particular, we demonstrate that increasingly well-separated clusters are identified as the dimensionality increases, when no such clusters exist. Furthermore, in a case of true bimodality, increasing the dimensionality makes identifying the correct...
A biologically inspired approach to feasible gait learning for a hexapod robot
The objective of this paper is to develop feasible gait patterns that could be used to control a real hexapod walking robot. These gaits should enable the fastest movement that is possible with the given robot's mechanics and drives on a flat terrain. Biological inspirations are commonly used in the design of walking robots and their control algorithms. However, legged robots differ significantly from their biological counterparts. Hence we believe that gait patterns should be learned using the...
A blind definition of shape
In this note, we propose a general definition of shape which is both compatible with the one proposed in phenomenology (gestaltism) and with a computer vision implementation. We reverse the usual order in Computer Vision. We do not define “shape recognition” as a task which requires a “model” pattern which is searched in all images of a certain kind. We give instead a “blind” definition of shapes relying only on invariance and repetition arguments. Given a set of images , we call shape of this...
A blind definition of shape
In this note, we propose a general definition of shape which is both compatible with the one proposed in phenomenology (gestaltism) and with a computer vision implementation. We reverse the usual order in Computer Vision. We do not define “shape recognition" as a task which requires a “model" pattern which is searched in all images of a certain kind. We give instead a “blind" definition of shapes relying only on invariance and repetition arguments. Given a set of images , we call shape of this...
A bound for the rank-one transient of inhomogeneous matrix products in special case
We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.
A bound for the Steiner tree problem in graphs
A bound for the -equivalence problem of polynomial D0L systems
We give a bound for the -equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.
A bound for the ω-equivalence problem of polynomial D0L systems
We give a bound for the ω-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.
A bound on correlation immunity.
A branch-and-cut algorithm for a resource-constrained scheduling problem
This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance,...