MPI-INF D1 Publications: Proceedings Article: A Polynomial-Time Fragment of Dominance Constraints

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

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

Action:

Options:

Goto entry point

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
Attachment(s):	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

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

Attachment Section

View attachments here:

151.pdf

Mehlhorn151.pdf