Order-Invariant Types and their Applications
Author
Abstract
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, hut 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 NISO properties are expressible in IMO
Patrocinador
Millennium Nucleus Center for Semantic Web Research
NC120004
EPSRC
J015377
M025268
Indexation
Artículo de publicación ISI
Quote Item
Logical Methods in Computer Science Vol. 12(1:9)2016, pp. 1–17
Collections
The following license files are associated with this item: