CROSS-MOMENTS COMPUTATION FOR STOCHASTIC CONTEXT-FREE GRAMMARS

DOI10.22190/FUMI1801041IzbMATH Open1474.68164arXiv1108.0353OpenAlexW2964102688MaRDI 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)

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.

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

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

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)

Cites Work

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

Cited In (2)

• A new one pass algorithm for estimating stochastic context-free grammars
• On a matrix of first moments for decomposable stochastic CF-grammar

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)