OBDD 일반화한 트리 결정 다이어그램 모델 제안

Florent Capelli 등 5명의 연구진은 불린 함수 모델링을 위한 트리 결정 다이어그램(TDD)을 제안했다. 이는 순서화된 이진 결정 다이어그램(OBDD)의 일반화된 형태로, structured d-DNNF의 제한된 버전이다. TDD는 vtree T를 준수하는 d-DNNF 구조를 기반으로 한다. 연구진은 TDD가 OBDD와 동일한 연산 효율성을 제공한다고 밝혔다. 모델 카운팅, 열거, 조건부 처리, 적용 등의 작업에서 동등한 성능을 보이면서도 더 간결한 표현이 가능하다. 특히 트리폭 k인 CNF 공식을 고정 매개변수 처리 가능(FPT) 크기의 TDD로 표현할 수 있는데, 이는 기존 OBDD로는 불가능한 것으로 알려져 있다. 연구진은 CNF 공식을 결정적 TDD로 컴파일하는 상향식 컴파일 방법의 복잡도를 분석하고, 이를 Bova와 Szeider가 도입한 팩터 폭(factor width) 개념과 연관지었다. 이 연구는 SAT26 학회에 제출되었다.