English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Determining the Consistency of Partial Tree Descriptions

MPS-Authors
/persons/resource/persons44150

Bodirsky,  Manuel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44874

Kutz,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.