Manuel Bodirsky
Determining the Consistency of Partial Tree Descriptions
With Martin Kutz. In Artificial Intelligence, 57(1), 109-125. A conference version of this paper appeared under the title "Pure Dominance Constraints" in STACS02.
Abstract
We present an efficient algorithm that checks 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 that was 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 input.
Download
Download: a post-print is available in pdf.
