On the Computation of Distances for Probabilistic Context-Free Grammars

摘要: Probabilistic context-free grammars (PCFGs) are used to define distributions over strings, and powerful modelling tools in a number of areas, including natural language processing, software engineering, model checking, bio-informatics, pattern recognition. A common important question is that comparing the generated or modelled by these grammars: this done through checking equivalence computing distances. Two PCFGs equivalent if every string has identical probability with both grammars. This also means distance (whichever norm used) null. It known problem interreducible multiple ambiguity for grammars, long-standing open question. In work, we prove distances corresponds solving undecidable questions: case L1, L2 norm, variation Kullback-Leibler divergence. more results less negative: 1. The most probable can be computed, and, 2. Chebyshev (where between two maximum difference probabilities all strings) problem.