hide
Free keywords:
-
Abstract:
We present an efficient algorithm that decides the consistency of partial
descriptions of ordered trees. The constraint language of these descriptions
was introduced by Cornell in computational linguistics; the constraints specify
for pairs of nodes sets of admissible relative positions in an ordered tree.
Cornell asked for an algorithm to find a tree structure satisfying these
constraints. This computational problem generalizes the common-supertree
problem studied in phylogenetic analysis, and also generalizes the network
consistency problem of the so-called left-linear point algebra. We present the
first polynomial time algorithm for Cornell's problem, which runs in time O(mn)
, where m is the number of constraints and n the number of variables in the
constraint.
