Datensatz

Zusammenfassung

Dominance constraints are logical
tree descriptions originating from automata theory that have multiple
applications in computational linguistics. The satisfiability problem
of dominance constraints is NP-complete. In most applications,
however, only \emph{normal} dominance constraints are used. The
satisfiability problem of normal dominance constraints can be reduced
in linear time to the configuration problem of dominance graphs, as
shown recently. In this paper, we give a polynomial time algorithm
testing configurability of dominance graphs (and thus satisfiability
of normal dominance constraints). Previous to our work no polynomial
time algorithms were known.