# Publication details

##
Ordering Constraints over Feature Trees Expressed in Second-order Monadic Logic

Martin Müller, Joachim Niehren

Information and Computation 159(1/2):22-58, 2000

The system FT of ordering constraints over feature trees has
been introduced as an extension of the system FT of equality
constraints over feature trees. While the first-order theory of FT
is well understood, only few complexity and decidability results are
known for fragments of the first-order theory of
FT$_leq$.
We
introduce a new handle for such decidability questions by
showing how to express ordering constraints over feature trees in
second-order monadic logic (S2S or WS2S). Our relationship implies
a new decidability
result for feature logics, namely that the entailment problem of
FT$_leq$
with existential quantifiers
$phi_1models exists x_1ldotsexists x_n phi_2$
is decidable. We also show that
this problem is PSPACE-hard even though the quantifier-free case can
be solved in cubic time. To our knowledge, this is the first time
that a non-trivial decidability result of feature logic is reduced
to Rabins famous tree theorem.

Download PDF
Show BibTeX

@ARTICLE{SWSJournal99,
title = {Ordering Constraints over Feature Trees Expressed in Second-order Monadic Logic},
author = {Martin M{\"u}ller and Joachim Niehren},
year = {2000},
journal = {{Information and Computation}},
volume = {{159}},
pages = {{22--58}},
number = {{1/2}},
note = {{Special Issue on {RTA} 1998}},
}

Login to edit

Webmaster,
Wed Sep 16 10:47:00 2009