Combinatorial problems in the theory of complexity of algorithmic nets without cycles for simple computers
Combinatorial properties of infinite words associated with cut-and-project sequences
The aim of this article is to study certain combinatorial properties of infinite binary and ternary words associated to cut-and-project sequences. We consider here the cut-and-project scheme in two dimensions with general orientation of the projecting subspaces. We prove that a cut-and-project sequence arising in such a setting has always either two or three types of distances between adjacent points. A cut-and-project sequence thus determines in a natural way a symbolic sequence (infinite word)...
Combinatorial properties of one-dimensional arrangements.
Combinatorial properties of texts
Combinatorics of singly-repairable families.
Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain
This paper presents the approach that we developed to solve the ROADEF 2003 challenge problem. This work is part of a research program whose aim is to study the benefits and the computer-aided generation of hybrid solutions that mix constraint programming and meta-heuristics, such as large neighborhood search (LNS). This paper focuses on three contributions that were obtained during this project: an improved method for propagating Hamiltonian chain constraints, a fresh look at limited discrepancy...
Comments on the analysis of parameters in a Random Graph Model
Comparing Complexity Functions of a Language and Its Extendable Part
Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.
Compatibility relations on codes and free monoids
A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an (R,S)-code and an (R,S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations....
Competitive colorings of oriented graphs.
Complementary equations and Wythoff sequences.
Complete characterization of substitution invariant Sturmian sequences.
Complete subgraphs of bipartite graphs and applications to trace languages
Complexité algébrique
Complexité de problèmes liés aux graphes sans circuit
Complexité de suites engendrées par des récurrences unipotentes
Complexité et automates cellulaires linéaires
Complexité et automates cellulaires linéaires
The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in , and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.
Complexity and special factors. (Complexité et facteurs spéciaux.)
Complexity of Hartman sequences
Let be an ergodic translation on the compact group and a continuity set, i.e. a subset with topological boundary of Haar measure 0. An infinite binary sequence defined by if and otherwise, is called a Hartman sequence. This paper studies the growth rate of , where denotes the number of binary words of length occurring in . The growth rate is always subexponential and this result is optimal. If is an ergodic translation