CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS

DOI10.22190/FUMI1801041IzbMATH Open1474.68164OpenAlexW2964102688MaRDI QIDQ5896876FDOQ5896876

Authors Velimir M. Ilić, Miroslav Ćirić, Miomir S. Stanković 

Publication date 5 May 2021

Published in Facta Universitatis, Series: Mathematics and Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.0353

zbMATH Keywords

stochastic context-free grammarcross-momentslanguage of grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Grammars and rewriting systems (68Q42)

Abstract: In this paper we consider the problem of efficient computation of cross-moments of a vector random variable represented by a stochastic context-free grammar. Two types of cross-moments are discussed. The sample space for the first one is the set of all derivations of the context-free grammar, and the sample space for the second one is the set of all derivations which generate a string belonging to the language of the grammar. In the past, this problem was widely studied, but mainly for the cross-moments of scalar variables and up to the second order. This paper presents new algorithms for computing the cross-moments of an arbitrary order, and the previously developed ones are derived as special cases.

Recommendations

• Cross-moments computation for stochastic context-free grammars
• On a matrix of first moments for decomposable stochastic CF-grammar
• Consistency of stochastic context-free grammars
• scientific article; zbMATH DE number 1670723
• STRUCTURAL HIDDEN MARKOV MODELS BASED ON STOCHASTIC CONTEXT-FREE GRAMMARS
• scientific article; zbMATH DE number 1670716
• Stochastic context-free grammars, regular languages, and newton's method

Cites work

• scientific article; zbMATH DE number 3731374 (Why is no real title available?)
• scientific article; zbMATH DE number 1232914 (Why is no real title available?)
• scientific article; zbMATH DE number 907008 (Why is no real title available?)
• Applying Probability Measures to Abstract Languages
• Computation of cross-moments using message passing over factor graphs
• Computation of distances for regular and context-free probabilistic languages
• Computing abstract decorations of parse forests using dynamic programming and algebraic power series
• Computing the relative entropy between regular tree languages
• Entropy Message Passing
• Matrix Analysis
• Moments of string and derivation lengths of stochastic context-free grammars
• ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATA
• Probabilistic parsing
• Products of weighted logic programs
• Rational kernels: theory and algorithms
• The Fourth Moment Method

Cited in

(5)

• Cross-moments computation for stochastic context-free grammars
• Computation of moments for probabilistic finite-state automata
• Computation of cross-moments using message passing over factor graphs
• On a matrix of first moments for decomposable stochastic CF-grammar
• A new one pass algorithm for estimating stochastic context-free grammars

This page was built for publication: CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896876)