2007/03/31 by Thomas Colcombet, Christof Löding · 2 citations
Computer Science · #cs.LO
paper · pdf · doi:10.2168/lmcs-3(2:4)2007
published as Logical Methods in Computer Science, Volume 3, Issue 2 (May 4, 2007) lmcs:2221 · 36 pages
arxiv created 2007/05/04 · arxiv updated 2017/01/11
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.