On the Sizes of Decision Diagrams Representing the Set of All Parse Trees of a Context-free Grammar


Masaaki Nishino, Kei Amii, Akihiro Yamamoto ;
Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, PMLR 73:153-164, 2017.


In this paper, we analyze the size of decision diagrams (DD) representing the set of all parse trees of a context-free grammar (CFG). CFG is widely used in the field of natural language processing and bioinformatics to estimate the hidden structures of sequence data. A decision diagram is a data structure that represents a Boolean function in a concise form. By using DDs to represent the set of all parse trees, we can efficiently perform many useful operations over the parse trees, such as finding trees that satisfy additional constraints and finding the best parse tree. Since the time complexity of these operations depends on DD size, selecting an appropriate DD variant is important. Experiments on a simple CFG show that the Zero-suppressed Sentential Decision Diagram (ZSDD) is better than other DDs; we also give theoretical upper bounds on ZSDD size.

Related Material