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.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v73-kei-amii17a, title = {On the Sizes of Decision Diagrams Representing the Set of All Parse Trees of a Context-free Grammar}, author = {Nishino, Masaaki and Amii, Kei and Yamamoto, Akihiro}, booktitle = {Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks}, pages = {153--164}, year = {2017}, editor = {Hyttinen, Antti and Suzuki, Joe and Malone, Brandon}, volume = {73}, series = {Proceedings of Machine Learning Research}, month = {20--22 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v73/kei-amii17a/kei-amii17a.pdf}, url = {https://proceedings.mlr.press/v73/kei-amii17a.html}, abstract = { 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.} }
Endnote
%0 Conference Paper %T On the Sizes of Decision Diagrams Representing the Set of All Parse Trees of a Context-free Grammar %A Masaaki Nishino %A Kei Amii %A Akihiro Yamamoto %B Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks %C Proceedings of Machine Learning Research %D 2017 %E Antti Hyttinen %E Joe Suzuki %E Brandon Malone %F pmlr-v73-kei-amii17a %I PMLR %P 153--164 %U https://proceedings.mlr.press/v73/kei-amii17a.html %V 73 %X 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.
APA
Nishino, M., Amii, K. & Yamamoto, A.. (2017). On the Sizes of Decision Diagrams Representing the Set of All Parse Trees of a Context-free Grammar. Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, in Proceedings of Machine Learning Research 73:153-164 Available from https://proceedings.mlr.press/v73/kei-amii17a.html.

Related Material