On the Computation of Distances for Probabilistic Context-Free Grammars
Preprint
Abstract
Probabilistic context-free grammars (PCFGs) are used to define distributions over strings, and are powerful modelling tools in a number of areas, including natural language processing, software engineering, model checking, bio-informatics, and pattern recognition. A common important question is that of comparing the distributions generated or modelled by these grammars: this is done through checking language equivalence and computing distances. Two PCFGs are language equivalent if every string has identical probability with both grammars. This also means that the distance (whichever norm is used) is null. It is known that the language equivalence problem is interreducible with that of multiple ambiguity for context-free grammars, a long-standing open question. In this work, we prove that computing distances corresponds to solving undecidable questions: this is the case for the L1, L2 norm, the variation distance and the Kullback-Leibler divergence. Two more results are less negative: 1. The most probable string can be computed, and, 2. The Chebyshev distance (where the distance between two distributions is the maximum difference of probabilities over all strings) is interreducible with the language equivalence problem.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Language equivalence of probabilistic pushdown automataInformation and Computation, 2014
- Consistency of stochastic context-free grammarsMathematical and Computer Modelling, 2010
- ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATAInternational Journal of Foundations of Computer Science, 2008
- Estimation of stochastic context-free grammars and their use as language modelsComputer Speech & Language, 2005
- The consensus string problem and the complexity of comparing hidden Markov modelsJournal of Computer and System Sciences, 2002
- RNA MODELING BY COMBINING STOCHASTIC CONTEXT-FREE GRAMMARS AND n-GRAM MODELSInternational Journal of Pattern Recognition and Artificial Intelligence, 2002
- Accurate computation of the relative entropy between stochastic regular grammarsRAIRO - Theoretical Informatics and Applications, 1997
- Stochastic context-free grammers for tRNA modelingNucleic Acids Research, 1994
- Semirings, Automata, Languages1986
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946