Abstract
We prove a weighted FefermanVaught decomposition theorem for disjoint unions and products of finite structures. The classical FefermanVaught Theorem describes how the evaluation of a first order sentence in a generalized product of relational structures can be reduced to the evaluation of sentences in the contributing structures and the index structure. The logic we employ for our weighted extension is based on the weighted MSO logic introduced by Droste and Gastin to obtain a Büchitype result for weighted automata. We show that for disjoint unions and products of structures, the evaluation of formulas from two respective fragments of the logic can be reduced to the evaluation of formulas in the contributing structures. We also prove that the respective restrictions are necessary. Surprisingly, for the case of disjoint unions, the fragment is the same as the one used in the Büchitype result of weighted automata. In fact, even the formulas used to show that the respective restrictions are necessary are the same in both cases. However, here proving that they do not allow for a FefermanVaughtlike decomposition is more complex and employs Ramsey's Theorem. We also show how translation schemes can be applied to go beyond disjoint unions and products.
BibTeX  Entry
@InProceedings{droste_et_al:LIPIcs:2018:9658,
author = {Manfred Droste and Erik Paul},
title = {{A FefermanVaught Decomposition Theorem for Weighted MSO Logic}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {76:176:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9658},
URN = {urn:nbn:de:0030drops96581},
doi = {10.4230/LIPIcs.MFCS.2018.76},
annote = {Keywords: Quantitative Logic, Quantitative Model Theory, FefermanVaught Theorem, Translation Scheme, Transduction}
}
Keywords: 

Quantitative Logic, Quantitative Model Theory, FefermanVaught Theorem, Translation Scheme, Transduction 
Collection: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 
Issue Date: 

2018 
Date of publication: 

27.08.2018 