Ordering constraints over feature trees expressed in second-order monadic logic
The language FTless than or equal to 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 decidability results are known for the first-order theory of FTless than or equal to. We introduce a new method for proving the decidability of fragments of the first-order theory of FTless than or equal to. This method is based on reduction to second order monadic logic that is decidable according to Rabin's famous tree theorem. The method applies to any fragment of the first-order theory of FTless than or equal to for which one can change the model towards sufficiently labeled feature trees-a class of trees that we introduce, As we show, the first order-theory of ordering constraints over sufficiently labeled feature trees is equivalent to second-order monadic logic (S2S for infinite and WS2S for finite feature trees). We apply our method for proving that entailment of FTless than or equal to with existential quantifiers phi(1) satisfies There Exists x(1) ... There Exists x(n)phi(2) is decidable. Previous results were restricted to entailment without existential quantifiers which can be solved in cubic lime. Meanwhile, entailment with existential quantifiers has been shown to be PSPACE-complele (for finite and infinite feature trees, respectively). (C) 2000 Academic Press.
second-order monadic logic decidability entailment feature logic tree orderings complexity