Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








Author, Editor

Author(s):

Koller, Alexander
Mehlhorn, Kurt
Niehren, Joachim

dblp
dblp
dblp



Editor(s):





BibTeX cite key*:

Koller-et-al:dominance-constraints

Title, Booktitle

Title*:

A Polynomial-Time Fragment of Dominance Constraints


151.pdf (242.13 KB); Mehlhorn151.pdf (224.1 KB)

Booktitle*:

Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics (ACL-00)

Event, URLs

URL of the conference:

http://www.cs.ust.hk/acl2000/

URL for downloading the paper:

http://acl.ldc.upenn.edu//P/P00/P00-1047.pdf

Event Address*:

Hong-Kong

Language:

English

Event Date*
(no longer used):

October, 3-6

Organization:

ACL

Event Start Date:

Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected

Event End Date:

Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected

Publisher

Name*:

Morgan Kaufmann

URL:

http://www.aclweb.org/

Address*:

San Francisco, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

368-375

Year*:

2000

VG Wort Pages:


ISBN/ISSN:

1-558-60729-3

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify \emph{normal} dominance constraints, a natural fragment whose satisfiability problem we show to be in polynomial time. We present a quadratic satisfiability algorithm and use it in another algorithm that enumerates solutions efficiently. Our result is useful for various applications of dominance constraints and related formalisms.

HyperLinks / References / URLs:

http://www.informatik.uni-trier.de/~ley/db/conf/acl/acl2000.html#KollerMN00



Download
Access Level:

Public

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



BibTeX Entry:

@INPROCEEDINGS{Koller-et-al:dominance-constraints,
AUTHOR = {Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim},
TITLE = {A Polynomial-Time Fragment of Dominance Constraints},
BOOKTITLE = {Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics (ACL-00)},
PUBLISHER = {Morgan Kaufmann},
YEAR = {2000},
ORGANIZATION = {ACL},
PAGES = {368--375},
ADDRESS = {Hong-Kong},
ISBN = {1-558-60729-3},
}


Entry last modified by Anja Becker, 03/02/2010
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)
Ingrid Finkler
Created
01/22/2001 11:55:55 AM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Tamara Hausmann
Tamara Hausmann
Edit Dates
22.01.2008 09:29:39
25.09.2006 09:25:31
31.08.2006 09:22:58
20.06.2006 11:59:36
04/25/2002 07:42:15 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn151.pdf151.pdf
View attachments here: