Thomas Colcombet ; Christof Löding - Transforming structures by set interpretations

lmcs:2221 - Logical Methods in Computer Science, May 4, 2007, Volume 3, Issue 2 - https://doi.org/10.2168/LMCS-3(2:4)2007
Transforming structures by set interpretationsArticle

Authors: Thomas Colcombet ORCID; Christof Löding

    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.


    Volume: Volume 3, Issue 2
    Published on: May 4, 2007
    Submitted on: July 18, 2006
    Keywords: Computer Science - Logic in Computer Science,F.4.1

    21 Documents citing this article

    Consultation statistics

    This page has been seen 979 times.
    This article's PDF has been downloaded 233 times.