Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Bodirsky, Manuel
Kutz, Martin

dblp
dblp

Not MPG Author(s):

Bodirsky, Manuel

BibTeX cite key*:

BodirskyKutz2007

Title

Title*:

Determining the consistency of partial tree descriptions

Journal

Journal Title*:

Artificial Intelligence

Journal's URL:

http://www.elsevier.com/wps/find/journaldescription.cws_home/505601/description#description

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0004-3702

Vol, No, pp, Date

Volume*:

171

Number:

2/3

Publishing Date:

February 2007

Pages*:

185-196

Number of
VG Pages:


Page Start:

185

Page End:

196

Sequence Number:


DOI:

10.1016/j.artint.2006.12.004

Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{BodirskyKutz2007,
AUTHOR = {Bodirsky, Manuel and Kutz, Martin},
TITLE = {Determining the consistency of partial tree descriptions},
JOURNAL = {Artificial Intelligence},
PUBLISHER = {Elsevier},
YEAR = {2007},
NUMBER = {2/3},
VOLUME = {171},
PAGES = {185--196},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {February},
ISBN = {0004-3702},
DOI = {10.1016/j.artint.2006.12.004},
}


Entry last modified by Anja Becker, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Anja Becker
Created
02/07/2008 02:50:45 PM
Revision
0.



Editor
Anja Becker



Edit Date
07.02.2008 14:55:33