Tree Decision Diagrams (TDD): Đột phá trong biểu diễn hàm Boolean và tổng quát hóa OBDD

Trong lĩnh vực khoa học máy tính và trí tuệ nhân tạo, việc biểu diễn và thao tác các hàm Boolean đóng vai trò cốt lõi trong nhiều bài toán như kiểm tra mô hình, lập kế hoạch và học máy. Biểu đồ quyết định nhị phân có thứ tự (OBDD) từ lâu đã là một cấu trúc dữ liệu tiêu chuẩn nhờ tính chuẩn hóa (canonical) và hiệu quả trong các thao tác. Tuy nhiên, OBDD có những hạn chế nhất định về kích thước biểu diễn đối với một số lớp hàm phức tạp.

Bài viết mới của các tác giả Florent Capelli và cộng sự đã đề xuất Tree Decision Diagrams (TDD) như một sự khái quát hóa (generalization) của OBDD. Về cơ bản, TDD có thể được xem là một sự hạn chế của structured d-DNNF (decomposable Negation Normal Form) dựa trên một vtree $T$. Điều này cho phép TDD kế thừa các đặc tính tính toán khả thi của OBDD như đếm mô hình (model counting), liệt kê (enumeration), điều kiện hóa (conditioning) và áp dụng (apply).

Điểm đột phá chính của TDD nằm ở tính súc tích (succinctness). Các nhà nghiên cứu đã chứng minh rằng các công thức Chuẩn dạng liên kết (CNF) có độ rộng cây (treewidth) là $k$ có thể được biểu diễn bởi các TDD có kích thước FPT (Fixed-Parameter Tractable). Đây là một tiến bộ đáng kể vì đối với OBDD, việc biểu diễn các công thức như vậy là không thể thực hiện được trong giới hạn kích thước FPT.

Nghiên cứu cũng đi sâu vào phân tích độ phức tạp của việc biên dịch (compile) các công thức CNF thành TDD xác định thông qua phương pháp biên dịch từ dưới lên (bottom-up compilation). Kết quả này được liên hệ với khái niệm "độ rộng yếu tố" (factor width) được giới thiệu bởi Bova và Szeider, mở ra hướng đi mới trong việc tối ưu hóa việc biên dịch tri thức trong các hệ thống AI.

Với những ưu điểm vượt trội này, TDD hứa hẹn sẽ trở thành một công cụ mạnh mẽ thay thế hoặc bổ sung cho OBDD trong các ứng dụng yêu cầu xử lý logic phức tạp và hiệu suất cao.