We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is $O\left(n \cdot \Delta^{-\frac{1}{k-2}}\right)$.

We study the decidability of the following problem: given p affine functions ƒ1,...,ƒp over $\mathbb{N}^k$ and two vectors $v_1, v_2\in\mathbb{N}^k$, is v2 reachable from v1 by successive iterations of ƒ1,...,ƒp (in this given order)? We show that this question is decidable for p = 1, 2 and undecidable for some fixed p.


A shuffle ideal is a language which is a finite union of languages of the form A*a1A*...A*ak where A is a finite alphabet and the ai's are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally we also present a characterization by subwords of the minimal automaton of a shuffle ideal and study the complexity of basic operations on shuffle ideals.

Here we give a characterization of Arnoux–Rauzy sequences by the way of the lexicographic orderings of their alphabet.

In this paper, we study two kinds of combinatorial objects, generalized integer partitions and tilings of 2D-gons (hexagons, octagons, decagons, etc.). We show that the sets of partitions, ordered with a simple dynamics, have the distributive lattice structure. Likewise, we show that the set of tilings of a 2D-gon is the disjoint union of distributive lattices which we describe. We also discuss the special case of linear integer partitions, for which other dynamical models exist.