Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Stochastic Context-Free Grammars, Regular Languages, and Newton's Method   We study the problem of computing the probability that a given stochastic
context-free grammar (SCFG), G, generates a string in a given regular language
L(D) (given by a DFA, D). This basic problem has a number of applications in
statistical natural language processing, and it is also a key necessary step
towards quantitative \omega-regular model checking of stochastic context-free
processes (equivalently, 1-exit recursive Markov chains, or stateless
probabilistic pushdown processes).
  We show that the probability that G generates a string in L(D) can be
computed to within arbitrary desired precision in polynomial time (in the
standard Turing model of computation), under a rather mild assumption about the
SCFG, G, and with no extra assumption about D. We show that this assumption is
satisfied for SCFG's whose rule probabilities are learned via the well-known
inside-outside (EM) algorithm for maximum-likelihood estimation (a standard
method for constructing SCFGs in statistical NLP and biological sequence
analysis). Thus, for these SCFGs the algorithm always runs in P-time.

13
The categories of this paper are: quant-ph
31
The categories of this paper are: ao-sci
20
The categories of this paper are: acc-phys
17
The categories of this paper are: q-fin
26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph
32
The categories of this paper are: atom-ph
7
The categories of this paper are: hep-th
28
The categories of this paper are: alg-geom
36
The categories of this paper are: cmp-lg
4
The categories of this paper are: cond-mat
9
The categories of this paper are: nlin
15
The categories of this paper are: nucl-ex
10
The categories of this paper are: q-bio
8
The categories of this paper are: hep-ex
14
The categories of this paper are: math-ph