Order-invariant types and their applications

DOI10.2168/LMCS-12(1:9)2016zbMATH Open1448.03021OpenAlexW2301245128MaRDI QIDQ2800972FDOQ2800972

Authors Pablo Barceló, Leonid Libkin 

Publication date 19 April 2016

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.04309

zbMATH Keywords

invariancetypesfinite model theory

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Automata and formal grammars in connection with logical questions (03D05)

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, 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.

Recommendations

• Order invariance on decomposable structures
• A short tutorial on order-invariant first-order logic
• Computer Science Logic
• Towards a characterization of order-invariant queries over tame graphs
• Order-invariant MSO is stronger than counting MSO in the finite

Cited In (7)

• Invariant inequalities in programs interpreted over an ordered field
• Improving Static Variable Orders Via Invariants
• Order-sorted inductive types
• Dynamically-typed computations for order-sorted equational presentations
• More on \(\mathrm{SOP}_1\) and \(\mathrm{SOP}_2\)
• A remark on order-types.
• Numbering matters

This page was built for publication: Order-invariant types and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800972)