2 results
Johan van Benthem ; Balder ten Cate ; Jouko Vaananen.
Lindstr\"om theorems characterize logics in terms of model-theoretic conditions such as Compactness and the L\"owenheim-Skolem property. Most existing characterizations of this kind concern extensions of first-order logic. But on the other hand, many logics relevant to computer science are fragments […]
Published on August 3, 2009
Amélie Gheerbrant ; Balder ten Cate.
We consider a specific class of tree structures that can represent basic structures in linguistics and computer science such as XML documents, parse trees, and treebanks, namely, finite node-labeled sibling-ordered trees. We present axiomatizations of the monadic second-order logic (MSO), monadic […]
Published on October 23, 2012