Transforming structures by set interpretations
<|reference_start|>Transforming structures by set interpretations: We consider a new kind of interpretation over relational structures: finite sets interpretations. Those interpretations are defined by weak monadic second-order (WMSO) formulas with free set variables. They transform a given structure into a structure with a domain consisting of finite sets of elements of the orignal structure. The definition of these interpretations directly implies that they send structures with a decidable WMSO theory to structures with a decidable first-order theory. In this paper, we investigate the expressive power of such interpretations applied to infinite deterministic trees. The results can be used in the study of automatic and tree-automatic structures.<|reference_end|>
@article{colcombet2007transforming,
    title={Transforming structures by set interpretations},
    author={Thomas Colcombet, Christof L"oding},
    journal={Logical Methods in Computer Science, Volume 3, Issue 2 (May 4,
  2007) lmcs:2221},
    year={2007},
    doi={10.2168/LMCS-3(2:4)2007},
    archivePrefix={arXiv},
    eprint={cs/0703039},
    primaryClass={cs.LO}
}