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

lmcs:2221 - Logical Methods in Computer Science, May 4, 2007, Volume 3, Issue 2
Transforming structures by set interpretations

Authors: Colcombet, Thomas and Löding, Christof

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.


Source : oai:arXiv.org:cs/0703039
DOI : 10.2168/LMCS-3(2:4)2007
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


Share

Consultation statistics

This page has been seen 36 times.
This article's PDF has been downloaded 11 times.