  We propose a concise function representation based on deterministic finite
state automata for exact most probable explanation and constrained optimization
tasks in graphical models. We then exploit our concise representation within
Bucket Elimination (BE). We denote our version of BE as FABE. FABE
significantly improves the performance of BE in terms of runtime and memory
requirements by minimizing redundancy. Results on most probable explanation and
weighted constraint satisfaction benchmarks show that FABE often outperforms
the state of the art, leading to significant runtime improvements (up to 5
orders of magnitude in our tests).
