An Extension of Muchnik's Theorem
Achim Bluemnsath · Journal of Logic and Computation · 2005
One of the strongest decidability results in logic is the theorem of Muchnik which allows one to transfer the decidability of the monadic second-order theory of a structure to the decidability of the MSO-theory of its iteration, a tree built of disjoint copies of the original structure. We present a generalization of Muchnik's result to stronger logics, namely guarded second-order logic and its extensions by counting quantifiers. We also establish a strong equivalence result between monadic least fixed-point logic (M-LFP) and MSO on trees by showing that whenever M-LFP and MSO coincide on a structure they also coincide on its iteration.