Barcelo, Pablo and Libkin, Leonid - Order-Invariant Types and Their Applications

lmcs:1632 - Logical Methods in Computer Science, April 1, 2016, Volume 12, Issue 1
Order-Invariant Types and Their Applications

Authors: Barcelo, Pablo and Libkin, Leonid

Our goal is to show that the standard model-theoretic concept of types can be applied in the study of order-invariant properties, i.e., properties definable in a logic in the presence of an auxiliary order relation, but not actually dependent on that order relation. This is somewhat surprising since order-invariant properties are more of a combinatorial rather than a logical object. We provide two applications of this notion. One is a proof, from the basic principles, of a theorem by Courcelle stating that over trees, order-invariant MSO properties are expressible in MSO with counting quantifiers. The other is an analog of the Feferman-Vaught theorem for order-invariant properties.


Source : oai:arXiv.org:1603.04309
DOI : 10.2168/LMCS-12(1:9)2016
Volume: Volume 12, Issue 1
Published on: April 1, 2016
Submitted on: August 8, 2015
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 117 times.
This article's PDF has been downloaded 35 times.