# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Determining the Consistency of Partial Tree Descriptions

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bodirsky, M., & Kutz, M. (2007). Determining the Consistency of Partial Tree Descriptions.* Artificial Intelligence,* *171*(2/3), 185-196. doi:10.1016/j.artint.2006.12.004.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1EE1-3

##### 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.