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
TÀI LIỆU MỚI ĐĂNG