de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

A Polynomial-Time Fragment of Dominance Constraints

MPG-Autoren

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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


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