David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
An investigation is made of certain quantitative and qualitative aspects of inherent ambiguity of context-free languages. Two main results are proved. The first asserts that for every integer k there are inherently k-ambiguous context-free subsets of abc*. This result is obtained as a corollary of a more general result concerning ambiguous presentations of semilinear sets. The second result asserts that inherent ambiguity can arise from the “nesting” property of context-free languages, as well as from the “pairwise matching” property. © 1970, ACM. All rights reserved.
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Miao Guo, Yong Tao Pei, et al.
WCITS 2011
Hong Guan, Saif Masood, et al.
SoCC 2023
Jihun Yun, Peng Zheng, et al.
ICML 2019