de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

A Polynomial-Time Fragment of Dominance Constraints

MPS-Authors

Koller,  Alexander
Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Koller, A., Mehlhorn, K., & Niehren, J. (2000). A Polynomial-Time Fragment of Dominance Constraints. In Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics (ACL-00) (pp. 368-375). San Francisco, USA: Morgan Kaufmann.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-3355-D
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.