A Polynomial-Time Fragment of Dominance Constraints

Alexander Koller, Kurt Mehlhorn, and Joachim Niehren

Proceedings of the 38th ACL, Hong Kong, 2000.

Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify the natural fragment of normal dominance constraints and show that its satisfiability problem is in deterministic polynomial time.

Download: Download (96 K)

BibTex Entry

@InProceedings{KolMehNie00, 
   author = {Alexander Koller and Kurt Mehlhorn and Joachim 
             Niehren}, 
   title  = {A Polynomial-Time Fragment of Dominance Constraints}, 
   year   = 2000, 
   booktitle = {Proceedings of the 38th ACL}, 
   address = {Hong Kong} 
} 

Back: Publications