Rakesh Mohan, Ramakant Nevatia
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.
Rakesh Mohan, Ramakant Nevatia
IEEE Transactions on Pattern Analysis and Machine Intelligence
Karan Bhanot, Ioana Baldini, et al.
AIES 2023
Rina Dechter, Kalev Kask, et al.
AAAI/IAAI 2002
Ge Gao, Qitong Gao, et al.
ICLR 2024