{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:16:16Z","timestamp":1777644976767,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2018,3,21]],"date-time":"2018-03-21T00:00:00Z","timestamp":1521590400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2018,3,21]]},"abstract":"<jats:p>In the early seventies, Shelah proposed a model-theoretic construction, nowadays called \u201citeration\u201d. 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 decidability 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\u2019s 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\u2019s iteration or Muchnik\u2019s 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\u2019s interation. In particular, the former hierarchy collapses at level 1.<\/jats:p>","DOI":"10.3233\/fi-2018-1667","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T12:16:10Z","timestamp":1521807370000},"page":"327-359","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Shelah-Stupp\u2019s Iteration and Muchnik\u2019s Iteration"],"prefix":"10.1177","volume":"159","author":[{"given":"Didier","family":"Caucal","sequence":"first","affiliation":[{"name":"LIGM\u2013CNRS, Universit\u00e9 Paris-Est, 77454 Marne-la-Vall\u00e9e Cedex 2, France."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Teodor","family":"Knapik","sequence":"additional","affiliation":[{"name":"ISEA, Universit\u00e9 de la Nouvelle Cal\u00e9donie, 98851 Noum\u00e9a Cedex, France."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2018,3,21]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2018-1667","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2018-1667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:30:54Z","timestamp":1777444254000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2018-1667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,21]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,3,21]]}},"alternative-id":["10.3233\/FI-2018-1667"],"URL":"https:\/\/doi.org\/10.3233\/fi-2018-1667","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,21]]}}}