Computation of distances for regular and context-free probabilistic languages

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

zbMATH Keywords

Kullback-Leibler divergenceprobabilistic finite automatalanguage entropyprobabilistic context-free languagesprobabilistic language distances

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

• KELLEY

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