On the Complexity of Language Membership for Probabilistic Words
43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026).
Abstract
We study the membership problem for context-free languages on probabilistic words, where each position specifies a probability distribution over letters independently. We investigate the complexity of computing the probability that a sampled word belongs to a given language, establishing tractability results for unambiguous and related classes of context-free languages, as well as hardness results beyond these classes.