AN EFFICIENT GRAPH ALGORITHM FOR DOMINANCE CONSTRAINTS

AN EFFICIENT GRAPH ALGORITHM FOR DOMINANCE CONSTRAINTS? ERNST ALTHAUS† , DENYS DUCHIER‡ , ALEXANDER KOLLER , KURT MEHLHORN† , JOACHIM NIEHREN‡ , AND SVEN THIEL† Abstract. 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 normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known. 1. Introduction. The dominance relation of a tree is the ancestor relation be- tween its nodes. Dominance constraints are logical descriptions of trees talking about the dominance relation. Dominance based tree descriptions were first used in automata theory in the six- ties [TW67], rediscovered in computational linguistics in the early eighties [MHF83], and investigated from a logical point of view in the early nineties [BRVS95]. Since then, they have found numerous applications in computational linguistics: they have been used for grammar formalisms [VS92, RVSW95, DT99, Per00], in natural lan- guage semantics [Mus95, ENRX98], and for discourse analysis [GW98]. The two most important computational tasks for dominance constraints are sat- isfiability testing – does the constraint describe a tree? – and enumerating solu- tions, i.e. the described trees. But as shown recently [KNT01], testing satisfiability is an NP-complete problem.

• variable names


• dominance constraints


• annotate variable


• let ?


• problem


• labeled variables


• normal dominance


• identify normal


• algorithm back


• graph algorithm