Shelah-Stupp's iteration and Muchnik's iteration

International audienceIn the early seventies, Shelah proposed a model-theoretic construction, nowadays called "iteration". This construction is an infinite replication in a tree-like manner where every vertex possesses its own copy of the original structure. Stupp proved that the decidabil-ity of the monadic second-order (MSO) theory is transferred from the original structure onto the iterated one. In its extended version discovered by Muchnik and introduced by Semenov, the iteration became popular in computer science logic thanks to a paper by Walukiewicz. Compared to the basic iteration, Muchnik's iteration has an additional unary predicate which, in every copy, marks the vertex that is the clone of the possessor of the copy. A widely spread belief that this extension is crucial is formally confirmed in the paper. Two hierarchies of relational structures generated from finite structures by MSO interpretations and either Shelah-Stupp's iteration or Muchnik's iteration are compared. It turns out that the two hierarchies coincide at level 1. Every level of the latter hierarchy is closed under Shelah-Stupp's interation. In particular, the former hierarchy collapses at level 1. It is also established that the relations from level 1 may be encoded as sets of tuples of words defined by certain relational expressions built on top of regular expressions