It is studied how taking the inverse image by a sliding block code affects the syntactic semigroup of a sofic subshift. The main tool are ζ-semigroups, considered as recognition structures for sofic subshifts. A new algebraic invariant is obtained for weak equivalence of sofic subshifts, by determining which classes of sofic subshifts naturally defined by pseudovarieties of finite semigroups are closed under weak equivalence. Among such classes are the classes of almost finite type subshifts and aperiodic subshifts. The algebraic invariant is compared with other robust conjugacy invariants.

We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.

J. Hromkovic et al. have given an elegant method to convert a regular expression of size n into an ε-free nondeterministic finite automaton having O(n) states and O(nlog2(n)) transitions. This method has been implemented efficiently in O(nlog2(n)) time by C. Hagenah and A. Muscholl. In this paper we extend this method to weighted regular expressions and we show that it can be achieved in O(nlog2(n)) time.

We first prove an extremal property of the infinite Fibonacci* word f: the family of the palindromic prefixes {hn | n ≥ 6} of f is not only a circular code but “almost” a comma-free one (see Prop. 12 in Sect. 4). We also extend to a more general situation the notion of a necklace introduced for the study of trinucleotides codes on the genetic alphabet, and we present a hierarchy relating two important classes of codes, the comma-free codes and the circular ones.

Cameron introduced the orbit algebra of a permutation group and conjectured that this algebra is an integral domain if and only if the group has no finite orbit. We prove that this conjecture holds and in fact that the age algebra of a relational structure R is an integral domain if and only if R is age-inexhaustible. We deduce these results from a combinatorial lemma asserting that if a product of two non-zero elements of a set algebra is zero then there is a finite common tranversal of their supports. The proof is built on Ramsey theorem and the integrity of a shuffle algebra.

We investigate the density and distribution behaviors of the chinese remainder representation pseudorank. We give a very strong approximation to density, and derive two efficient algorithms to carry out an exact count (census) of the bad pseudorank integers. One of these algorithms has been implemented, giving results in excellent agreement with our density analysis out to 5189-bit integers.

We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumäki on the characterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators, we prove that if H and K are two finitely generated submonoids generated by prefix sets such that the product automaton associated to $H \cap K$ has a given special property then $\widetilde{rk}(H \cap K) \leq \widetilde{rk}(H) \widetilde{rk}(K)$ where $\widetilde{rk}(L)=\max(0,rk(L)-1)$ for any submonoid L.

The LS (Look and Say) derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, LS( 1 1 2 3 3) = 2 1 1 2 2 3 (two 1, one 2, two 3). We start the study of the behaviour of binary words generated by morphisms under the LS operator, focusing in particular on the Fibonacci word.

We investigate the computational structure of the biological kinship assignment problem by abstracting away all biological details that are irrelevant to computation. The computational structure depends on phenotype space, which we formally define. We illustrate this approach by exhibiting an approximation algorithm for kinship assignment in the case of the Simpson index with a priori error bound and running time that is polynomial in the bit size of the population, but exponential in phenotype space size. This algorithm is based on a relaxed version of the assignment problem, where fractional assignments (over the reals) are permitted.

In this paper, we characterize the substitutions over a three-letter alphabet which generate a ultimately periodic sequence.


 (1) Shepherdson proved that a discrete unitary commutative semi-ring A+ satisfies IE0 (induction scheme restricted to quantifier free formulas) iff A is integral part of a real closed field; and Berarducci asked about extensions of this criterion when exponentiation is added to the language of rings. Let T range over axiom systems for ordered fields with exponentiation; for three values of T we provide a theory $_{\llcorner} T _{\lrcorner}$ in the language of rings plus exponentiation such that the models (A, expA) of $_{\llcorner} T _{\lrcorner}$ are all integral parts A of models M of T with A+ closed under expM and expA = expM | A+. Namely T = EXP, the basic theory of real exponential fields; T = EXP+ the Rolle and the intermediate value properties for all 2x-polynomials; and T = Texp, the complete theory of the field of reals with exponentiation. (2)$_{\llcorner}$Texp$_{\lrcorner}$ is recursively axiomatizable iff Texp is decidable. $_{\llcorner}$Texp$_{\lrcorner}$ implies LE0(xy) (least element principle for open formulas in the language <,+,x,-1,xy) but the reciprocal is an open question. $_{\llcorner}$Texp$_{\lrcorner}$ satisfies “provable polytime witnessing”: if $_{\llcorner} $Texp$_{\lrcorner}$ proves ∀x∃y : |y| < |x|k)R(x,y) (where $|y|:=_{\llcorner}$log(y)$_{\lrcorner}$, k < ω and R is an NP relation), then it proves ∀x R(x,ƒ(x)) for some polynomial time function f. (3) We introduce “blunt” axioms for Arithmetics: axioms which do as if every real number was a fraction (or even a dyadic number). The falsity of such a contention in the standard model of the integers does not mean inconsistency; and bluntness has both a heuristic interest and a simplifying effect on many questions – in particular we prove that the blunt version of $_{\llcorner} $Texp$_{\lrcorner}$ is a conservative extension of $_{\llcorner} $Texp$_{\lrcorner}$ for sentences in ∀Δ0(xy) (universal quantifications of bounded formulas in the language of rings plus xy). Blunt Arithmetics – which can be extended to a much richer language – could become a useful tool in the non standard approach to discrete geometry, to modelization and to approximate computation with reals.


A set T ⊆ L is a Parikh test set of L if c(T) is a test set of c(L). We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.

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. We generalize the stability criterion of Schützenberger and Tilson's closure result for (R,S)-free monoids. The (R,S)-free hull of a set of words is introduced and we show how it can be computed. We prove a defect theorem for (R,S)-free hulls. In addition, a defect theorem of partial words is proved as a corollary.

The cyclic shift of a language L, defined as SHIFT(L) = {vu | uv ∈ L}, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov's pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl.11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! . 2(n-1)(n-2), which shows that the state complexity of cyclic shift is 2n2+ nlogn - O(n) for alphabets with at least 4 letters. For 2- and 3-letter alphabets, we prove $2^{\Theta(n^2)}$ state complexity. We also establish a tight 2n2+1 lower bound for the nondeterministic state complexity of this operation using a binary alphabet.

We consider logics on $\mathbb{Z}$ and $\mathbb{N}$ which are weaker than Presburger arithmetic and we settle the following decision problem: given a k-ary relation on $\mathbb{Z}$ and $\mathbb{N}$ which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.

A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of $\mathbb{Z}$-rational sequences.

We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.

We prove that there exists a structure M whose monadic second order theory is decidable, and such that the first-order theory of every expansion of M by a constant is undecidable. 


We design algorithms of “optimal" data complexity for several natural problems about first-order queries on structures of bounded degree. For that purpose, we first introduce a framework to deal with logical or combinatorial problems R ⊂ I x O whose instances x ∈ I may admit of several solutions R(x) = {y ∈ O : (x,y) ∈ R}. One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution y ∈ R(x); enumerate without repetition each solution yj in some specific linear order y0 < y1 < ... < yn-1 where R(x) = {y0,...,yn-1}; compute the solution yj of rankj in the linear order <. Algorithms of “minimal" data complexity are presented for the following problems: given any first-order formula $\varphi(\bar{v})$ and any structure S of bounded degree: (1) compute a random element of $\varphi(S)=\{\bar{a}: (S,\bar{a})\models\varphi(\bar{v})\}$; (2) compute the jth element of $\varphi(S)$ for some linear order of $\varphi(S)$; (3) enumerate the elements of $\varphi(S)$ in lexicographical order. More precisely, we prove that, for any fixed formula φ, the above problem (1) (resp. (2), (3)) can be computed within average constant time (resp. within constant time, with constant delay) after a linear (O(|S|)) precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.

We propose a variation of Wythoff's game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time.