Projects per year
Abstract / Description of output
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.
Original language | English |
---|---|
Number of pages | 18 |
Journal | Logical Methods in Computer Science |
DOIs | |
Publication status | Published - 1 Apr 2016 |
Fingerprint
Dive into the research topics of 'Order-Invariant Types and their Applications'. Together they form a unique fingerprint.Projects
- 2 Finished
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research
-