Identification d'un phénomène bactériologique
Identifying codes with small radius in some infinite regular graphs.
Imbalances in Arnoux-Rauzy sequences
In a 1982 paper Rauzy showed that the subshift generated by the morphism , and is a natural coding of a rotation on the two-dimensional torus , i.e., is measure-theoretically conjugate to an exchange of three fractal domains on a compact set in each domain being translated by the same vector modulo a lattice. It was believed more generally that each sequence of block complexity satisfying a combinatorial criterion known as the condition of Arnoux and Rauzy codes the orbit of a point...
Implementation of directed acyclic word graph
An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text is a minimal automaton that accepts all substrings of a text , so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i. e. vertices,...
Improved bounds on the length of maximal abelian square-free words.
Improved bounds on the number of ternary square-free words.
Improved expansion of random Cayley graphs.
Improved inclusion-exclusion identities via closure operators.
Improved lower bounds on the approximability of the traveling salesman problem
Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless ). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, Delta-TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively,...
In memoriam: Philippe Flajolet, the father of analytic combinatorics
In memoriam: Philippe Flajolet, the father of analytic combinatorics
Independence number and degree bounded spanning tree.
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
Independent sets on path-schemes.
Inductive computations on graphs defined by clique-width expressions
Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function D, if G is a graph with n vertices and of clique-width at most k, where k is fixed, we can associate with each vertex x of G a piece of information (bit sequence) lab(x) of length O(log2(n)) such that we can compute D in constant time, using only the labels...
Infinite periodic discrete minimal surfaces without self-intersections.
Infinite periodic points of endomorphisms over special confluent rewriting systems
We consider endomorphisms of a monoid defined by a special confluent rewriting system that admit a continuous extension to the completion given by reduced infinite words, and study from a dynamical viewpoint the nature of their infinite periodic points. For prefix-convergent endomorphisms and expanding endomorphisms, we determine the structure of the set of all infinite periodic points in terms of adherence values, bound the periods and show that all regular periodic points are attractors.
Infinite words containing squares at every position
Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3.
Influence of modeling structure in probabilistic sequential decision problems
Markov Decision Processes (MDPs) are a classical framework for stochastic sequential decision problems, based on an enumerated state space representation. More compact and structured representations have been proposed: factorization techniques use state variables representations, while decomposition techniques are based on a partition of the state space into sub-regions and take advantage of the resulting structure of the state transition graph. We use a family of probabilistic exploration-like...