Báo cáo khoa học: "A Polynomial-Time Fragment of Dominance Constraints"

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.

TÀI LIỆU LIÊN QUAN
TÀI LIỆU XEM NHIỀU