MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.cs.ust.hk/acl2000/
Downloading URL:
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
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