# Publication details

##
Feature Trees over Arbitrary Structures

Ralf Treinen

Specifying Syntactic Structures, CSLI Publications, 1996

This paper presents a family of first order feature tree theories, indexed by the theory of the feature labels used to build the trees. A
given feature label theory, which is required to carry an appropriate
notion of sets, is conservatively extended to a theory of feature trees
with the predicates x[t]y (feature t leads from the root of tree x to
the tree y), where we have to require t to be a ground term, and
(feature t is defined at the root of tree x). In the latter
case, t might be a variable. Together with the notion of sets provided
by the feature label theory, this yields a first-class status of
arities.
We present a quantifier elimination procedure to reduce any sentence of
the feature tree theory to an equivalent sentence of the feature label
theory. Hence, if the feature label theory is decidable, the feature
tree theory is too.
If the feature label theory is the theory of infinitely many constants
and finite sets over infinitely many constants, we obtain an extension
of the feature theory CFT, giving first-class status to arities. As an
another application, we obtain decidability of the theory of feature
trees, where the feature labels are words, and where the language
includes the successor function on words, lexical comparison of words
and first-class status of arities.

Download PDF
Show BibTeX

@INCOLLECTION{Treinen:ArbFeat95,
title = {Feature Trees over Arbitrary Structures},
author = {Ralf Treinen},
year = {1996},
editor = {"Patrick Blackburn and Maarten de Rijke"},
publisher = {"CSLI Publications"},
booktitle = {Specifying Syntactic Structures},
series = {"Studies in Logic, Language and Information"},
note = {"To appear. Collection of selected papers from the Workshop on Logic, Structures and Syntax, Amsterdam, September 1994"},
}

Login to edit

Webmaster,
Wed Sep 16 10:47:00 2009