Computation of distances for regular and context-free probabilistic languages
From MaRDI portal
Publication:932320
DOI10.1016/j.tcs.2008.01.010zbMath1142.68043OpenAlexW2036421791MaRDI QIDQ932320
Mark-Jan Nederhof, Giorgio Satta
Publication date: 10 July 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.010
Kullback-Leibler divergenceprobabilistic finite automatalanguage entropyprobabilistic context-free languagesprobabilistic language distances
Related Items (6)
Computation of moments for probabilistic finite-state automata ⋮ A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars ⋮ Regular Language Distance and Entropy ⋮ Definitions and properties of entropy and distance for regular languages ⋮ CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS ⋮ CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing the relative entropy between regular tree languages
- Pattern synthesis. Lectures in pattern theory. Vol. I
- The consensus string problem and the complexity of comparing hidden Markov models.
- Moments of string and derivation lengths of stochastic context-free grammars
- Weighted Deductive Parsing and Knuth's Algorithm
- A General Technique to Train Language Models on Language Models
- Efficient Computation of the Relative Entropy of Probabilistic Automata
- Analysis of the binary complexity of asymptotically fast algorithms for linear system solving
- Biological Sequence Analysis
- Accurate computation of the relative entropy between stochastic regular grammars
- Entropies of probabilistic grammars
- Probabilistic grammars and automata
- Applying Probability Measures to Abstract Languages
- STACS 2005
- On the Computation of Some Standard Distances Between Probabilistic Automata
This page was built for publication: Computation of distances for regular and context-free probabilistic languages