On the Complexity of Language Membership for Probabilistic Words

Antoine Amarilli, Mikaël Monet, Paul Raphaël +1

We study the membership problem to context-free languages (CFLs) on probabilistic words, that specify for each position a probability distribution on the letters. Our task is to co…