text:
\section{Introduction}

Every language (natural or programming) is defined by grammar, i.e., a set of allowed symbols and rules that specify how the symbols can form longer strings (e.g., words or sentences). In context-free grammars (CFGs)~\cite{sipser2006}, the rules must not take the context of symbols into account, so rules such as \textit{i before e except after c} are not possible (since \textit{after c} defines the context of the rule). Thus, CFGs are inappropriate for natural languages and are regularly used to specify programming languages. Despite that, CFGs are an established and widely used tool for natural language processing, e.g.,~\cite{nltk, nlp-cfg-seki, nlp-cfg-thorsteinsson}.

Their extension, probabilistic (also known as stochastic) context-free grammars (PCFGs), assign probabilities to the rules, leading to the probability of deriving a string. \textit{Consistent} PCFG defines a probability distribution over the space of strings in the grammar language, i.e., the probabilities of the strings derived by the consistent grammar sum up to 1. The ability of CFGs to specify languages and PCGs to specify probability distributions over strings in the language make them a common choice for generative models in machine learning~\cite{kusner2017,duvwnaud2013}, and also symbolic regression~\cite{todorovski1997,brence2021}.

Given a set of observations $(\bm{x}, y)$, the goal of symbolic regression is to discover a closed-form equation of the form $y = f(\bm{x})$ that sufficiently well explains the target variable $y$ in terms of independent variables $\bm{x} = (x_1, \dots, x_n)$. PCFGs can be used to specify the probability distribution over the space of candidate expressions for the right-hand side of the equation. Then, equations can be discovered by following the generate-and-test paradigm~\cite{brence2021}. In the generating step, expressions with generic constants are sampled, e.g., $c_1 x_1 + c_2 x_2$ with the constants $c_1$ and $c_2$. In the second (i.e., testing) step, numerical optimization is used to fit the values of $c_1$ and $c_2$ against the given set of observations. The probabilities of the grammar rules are set so that generating simpler arithmetic expressions is more probable than generating complex ones.

This use case of PCFGs is the main focus of the paper. We are interested in PCFGs generating algebraic expressions. More specifically, we would like to compute the probability that a given PCFG derives a given expression $e$. In general, such a computation can involve summing up the probabilities of an infinite number of derivations of $e$, which happens in the following two scenarios. On the one hand, the grammar might be \textit{ambiguous}, i.e., it can derive $e$ in more than one way.
On the other hand, multiple stings can be equivalent to the same algebraic expression. For example, strings \texttt{c x + d} and \texttt{d + c x} are different but equivalent to the same expression $c x + d$. The probability of the latter is the sum of the probabilities of all the strings derived from the grammar being equivalent to $c x + d$.

Thus, the article's main aim is to design an algorithm for calculating the probability of deriving an expression $e$ from an expression-generating PCFG $G$. The purpose is achieved through three key contributions. The first contribution of the article is a formal definition of the equivalence relation $\sim$ between strings that relates strings that are equivalent to the same expression. The second contribution is the proof that an algorithm that would compute the probability of an equivalence class $[w]_\sim$ of a given string $w$ for any given PCFG does not exist. The article's third contribution is an algorithm for specific PCFGs generating linear, polynomial, and rational expressions. We analyze the algorithm's computational complexity and propose an approximate version that efficiently approximates the actual probability for cases when the exact calculation is infeasible.

The rest of the article is organized as follows. Section~2 introduces CFGs, PCFGs, and the notation used in the article. In Section~3, we introduce expression-generating grammars and their use for symbolic regression, formally define an equivalence relation among strings of an expression-generating grammar, and define expressions as equivalence classes of the relation. Section~4 proves that the algorithm for calculating the probability of deriving a given expression with any given PCFG does not exist and presents exact and approximate algorithms for grammars generating linear, polynomial, and rational expressions. Section~5 concludes the paper with a summary and outline of directions for further research.

\section{Probabilistic context-free grammars}

In this section, we first define context-free grammars and language of strings that can be derived with a given grammar. In continuation, we define probabilistic context-free grammars and probabilities of strings in the grammar language. Finally, we discuss the issue of calculating a probability of a string in the grammar language. Table~\ref{tab:notation} enlists and defines the semantics of the notation symbols that we use in the rest of the article.

\begin{table}[!htb]
    \centering
    \begin{tabular}{l|p{0.75\textwidth}}
        Symbol & Definition and semantics \\
        \hline
        $V^*$ & the set of all strings (finite sequences) with elements from $V$, i.e., $V^*=\{a_1 \dotsm a_n \mid a_i \in V \land n \in \mathbb{N}_0 \}$ \\
        $\varepsilon$ & the empty string, $\varepsilon \in V^*$ for any set $V$ \\
		\hline
        $T$ & the set of terminal symbols, also terminals \\
        \texttt{a}, \texttt{x}, \texttt{y} & arbitrary terminals, elements of $T$ \\
        $w$, $u$, $v$ & arbitrary strings of terminals (words), elements of $T^*$ \\
		\hline
        $N$ & the set of non-terminal symbols, also non-terminals \\
        $S$ & the starting non-terminal, element of $N$ \\
        $A$, $B$, $C$ & arbitrary non-terminals, elements of $N$ \\
		\hline
		$X$, $Y$, $Z$ & arbitrary non-terminals or terminals, elements of $\nut$ \\
		$\alpha$, $\beta$, $\gamma$ & arbitrary strings of terminals and non-terminals, elements of $(\nut)^{*}$ \\
		\hline
        $R$ & the set of grammar production rules \\
		$\rho$, $A \to \alpha$ & a grammar production rule, also rule, element of $R$ \\
		\hline
		$G$ & deterministic or probabilistic context-free grammar \\
		$\tau$ & grammar parse tree \\
        $p$, $q$, $r$ & probabilities \\
		\hline
    \end{tabular}
    \caption{The definitions and semantics of the notation symbols used throughout the article.}
    \label{tab:notation}
\end{table}

Let us first introduce the formal definition of a context-free grammar.
\begin{definition}
\label{def:cfg}
Let $N$ and $T$ be nonempty, finite disjoint sets and $S$ a distinguished element of $N$. Let $R \subseteq N \times (\nut{})^*$ be a left-total relation. A tuple $G = (N, T, S, R)$ is called \emph{context-free grammar (CFG)} with a set of non-terminal symbols $N$, terminal symbols $T$, start symbol $S$ and a set of production rules $R$.
\end{definition}
\noindent Note that in literature on context-free grammars, e.g., the standard textbook~\cite{sipser2006}, alternative symbols and notions can be used. The elements of $N$ can also be referred as variables (and denoted by $V$), the set $T$ can also be an alphabet (denoted by $\Sigma$), and the strings, derived by the grammar, are referred to as expressions. However, since the focus of the paper are grammars that generate mathematical expressions consisting of variables and constants, we are using the notation introduced in Table~\ref{tab:notation} and Definition~\ref{def:cfg}.

A production rule $(A, \alpha) \in R$ is often written as $A \to \alpha$, conveying the notion that $A$ can be rewritten with $\alpha$. For a rule $A \to \alpha \in R$ and strings $\beta, \gamma \in (\nut)^*$, we also write $\beta A \gamma \to \beta \alpha \gamma$ meaning that we can \emph{derive} the string $\beta \alpha \gamma$ from $\beta A \gamma$ using the rule $A \to \alpha$. The set of production rules $\{A \to \alpha_1, \dotsc, A \to \alpha_n\}$ for a non-terminal $A$ can be more compactly written as $A \to \alpha_1 \mid \cdots \mid \alpha_n$.

Given a CFG, we derive (also generate) a string of terminals (also word) as follows. We start with $S$ and choose an arbitrary rule $S \to \alpha \in R$ and replace $S$ with $\alpha$. In the iterative step, we choose a non-terminal symbol $A \in \alpha$, a rule $A \to \beta$, and replace $A$ with $\beta$. We repeat the iteration until the resulting string $\beta$ consists of terminals only. Since the relation $R$ is left-total (recall Definition~\ref{def:cfg}), we can always find at least one rule applicable in the iterative step. Below, we give a more formal definition of string generation.
\begin{definition}
\label{def:language}
A CFG $G = (N, T, S, R)$ \emph{derives} a string $w \in T^*$, if there exists a finite sequence $(\alpha_i)_{i = 1}^n$ of elements of $(\nut)^*$, such that $\alpha_1 = S$, $\alpha_n = w$, and $\alpha_i \to \alpha_{i+1}$, for all $1 \leq i < n$. The set $L(G)$ of all strings that $G$ derives is referred to as the \emph{language} of $G$.
\end{definition}

\noindent Let us illustrate the above definitions on a simple example.

\begin{ex}
\label{ex:basic-grammar}
Let $G=(\{S, A, B, C\}, \{\texttt{x},\texttt{y}\}, S, R)$ be a CFG with the following five production rules:
\begin{align*}
    S & \to AB, \\
    A & \to \mid \texttt{x}, \\
    B & \to C \mid \texttt{y}, \\
    C & \to \texttt{y}.
\end{align*}
The language of this grammar is a singleton $L(G) = \{\texttt{xy}\}$. A possible generating sequence for \texttt{xy} is $S \to AB \to \texttt{x}B \to  \texttt{xy}$.
\end{ex}

\noindent The generating sequence is often depicted with a parse (also derivation) tree.

\begin{definition}
\label{def:tree}
\emph{Parse tree} is a directed, rooted tree, such that
    \begin{itemize}
    \item its nodes are symbols from $\nut{}$: its root is $S$, its internal nodes are non-terminals from $N$, its leaves are terminals from $T$;
    \item children of an internal node $A \in N$ are the symbols in the string $\alpha \in (\nut)^*$, for some production rule $A \to \alpha\; \in R$, ordered from left to right in the same order as in $\alpha$.
    \end{itemize}
The string derived by a parse tree is the left-to-right sequence of its leaves, and is always an element of $L(G)$. For each $w \in L(G)$, there exist at least one parse tree $\tau$ generating $w$, which is denoted by $\str{\tau} = w$. If there is more than one parse tree for at least one string in $L(G)$, the grammar $G$ is \emph{ambiguous}. The set of all parse trees for a grammar $G$ is denoted by $\Psi(G)$.
\end{definition}

\begin{ex}
\label{ex:basic-tree}
Let $G$ be the grammar from Example~\ref{ex:basic-grammar}. Then, the set $\Psi(G)$ of parse trees derived by grammar $G$ consists of the following two elements:
$$
\begin{forest}
xx/.style={edge={white,line width=0pt}},
 [\hphantom{S}, xx
 [ $\tau_1 $\text{ =} , xx]
 ]
 \end{forest}
\begin{forest}
 [$S$
 [$A$ [\texttt{x}]]
 [$B$ [\texttt{y}]]
 ]
\end{forest}\quad\quad
\begin{forest}
xx/.style={edge={white,line width=0pt}},
 [\hphantom{S}, xx
 [\text{and}, xx]
 ]
 \end{forest}
\quad\quad
\begin{forest}
xx/.style={edge={white,line width=0pt}},
 [\hphantom{S}, xx
 [ $\tau_2 $\text{ =} , xx]
 ]
 \end{forest}
\begin{forest}
 [$S$
 [$A$ [\texttt{x} , tier=T]]
 [\hphantom{o}$B$   . [$C$ [\texttt{y}, tier=T]]]
 ]
\end{forest}
$$
Since, $\str{\tau_1} = \str{\tau_2} = \texttt{xy}$, $G$ is ambiguous.
\end{ex}

\subsection{Probabilistic context-free grammars}

We can extend context-free grammars to probabilistic context-free grammars by assigning probabilities to the production rules as follows.
\begin{definition}
\label{def:pcfg}
Let $G=(N, T, S, R)$ be a context-free grammar and $P \colon R \to [0,1]$ a mapping, such that
$$\sum_{i = 1}^{n} P(A \to \alpha_i) = 1,$$
for all $A\in N$ and the corresponding production rules $A\to \alpha_1 \mid \dots \mid \alpha_n$.
A pair $(G, P)$ is a \emph{probabilistic context-free grammar (PCFG)}.
\end{definition}

\noindent The probability distribution over the rules for $A \in N$ defines the probabilities with which we select one of the rules $A\to \alpha_1 \mid \dots \mid \alpha_n$ for rewriting the symbol $A$. We usually write rules and their probabilities as
$$A \to \alpha\; [P(A \to \alpha)] \quad \text{or} \quad A \xrightarrow{P(A \to \alpha)} \alpha,$$
and conveniently extend the domain of $P$ to $N\times (\nut{})^*$ with assuming that $P(\rho) = 0$ for $\rho \notin R$.
If we further assume that the production rules for deriving a string are being chosen independently from each other, we can define the probability of a given parse tree as follows.
\begin{definition}
\emph{Probability of a parse tree} $\tau$ from $G$ is defined as a product of probabilities of all the production rules in $\tau$, i.e.,
    $$
    P(\tau) = \prod_{\rho \in R} P(\rho)^{f_\tau(\rho)},
    $$
where  $f_\tau(\rho)$ denotes the frequency (number of appearances) of rule $\rho$ in $\tau$.
\end{definition}

\begin{ex}
\label{ex:basic-proba}
Let $G$ be a PCFG with start symbol $S$, terminal symbol \texttt{x} and two production rules $S \to SS\ [p] \mid \texttt{x}\ [1-p]$. String \texttt{x} is derived by the following two parse trees:
$$
\begin{forest}
xx/.style={edge={white,line width=0pt}},
 [\hphantom{S}, xx
 [ $\tau_1 $\text{ =} , xx]
 ]
 \end{forest}
\begin{forest}
 [$S$
[$S$ [$S$ [\texttt{x}, tier=T]]  [$S$ [\texttt{x}, tier=T]]]
[$S$ [\texttt{x}, tier=T]]
 ]
\end{forest}\quad\quad
\begin{forest}
xx/.style={edge={white,line width=0pt}},
 [\hphantom{S}, xx
 [\text{and}, xx]
 ]
 \end{forest}
\quad\quad
\begin{forest}
xx/.style={edge={white,line width=0pt}},
 [\hphantom{S}, xx
 [ $\tau_2 $\text{ =} , xx]
 ]
 \end{forest}
\begin{forest}
 [$S$
[$S$ [\texttt{x}, tier=T]]
[$S$ [$S$ [\texttt{x}, tier=T]]  [$S$ [\texttt{x}, tier=T]]]
 ]

\end{forest}
\begin{forest}
xx/.style={edge={white,line width=0pt}},
 [\hphantom{S}, xx
 [\hphantom{S}, xx
 [\text{.}, xx]
 ]
 ]
 \end{forest}
$$
In both trees, the rule $S \to SS$ appears twice and the rule $S\to \texttt{x}$ is used three times. Thus, $P(\tau_1) = P(\tau_2) = p^2(1-p)^3$.
\end{ex}

\noindent Following the example above,
we can compute the probability of deriving the string \texttt{x}: $P(\texttt{x}) = P(\tau_1) + P(\tau_2) = 2 p^2 (1-p)^3$. In general, we have
\begin{cor}
\emph{Probability of deriving a string} $w$ with grammar $G$ equals the sum of probabilities of all parsing trees that generate $w$, i.e.,
\begin{equation}
    \label{eq:p-word}
      P(w) = \sum \limits _{\tau:\; \str{\tau} = w} P(\tau).
\end{equation}
\end{cor}
\noindent Two remarks regarding the above formula need to be given. First, the sum $\sum_{w \in L(G)} P(w) = \sum_{\tau \in \Psi(G)} P(\tau)$ is finite, but might be strictly less than $1$, i.e., a string deriving process does not stop with a positive probability. See \ref{sec:appendix:examples} for an example. Second, the formula cannot be immediately implemented as an algorithm for calculating probabilities, since the sum might iterate over an infinite number of parse trees. In the next section, we further discuss the problem of calculating the probability of deriving a string $w \in L(G)$ with $G$.

\subsection{Probability of deriving a string}

We are interested in an algorithm that for a given input, consisting of a grammar $G$ and a string $w$, outputs $P(w)$. The sum~\eqref{eq:p-word} over all the parse trees deriving $w$ can not be immediately used in cases when infinite number of parse trees deriving $w$. Since $\nut{}$ and $R$ are finite sets, the set of parse trees generating $w$ can only be infinite, if at least one production rule leads to a branch with unlimited depth. In other words, there is a sequence of rules that overwrites a non-terminal symbol $A$ with a string $\alpha$ containing $A$. In the case of $G = (\{S\}, \{\texttt{x}\}, S, S \to S \mid \texttt{x})$, this sequence is simply $S\to S$.
\begin{definition}
\label{def:cycle}
    A \emph{cycle} in a parse tree is a branch $A \to \dotsb \to \alpha A\beta$, for some $\alpha, \beta\in (\nut{})^*$.
    If $\alpha = \beta = \epsilon$, the cycle is \emph{linear}. We define the \emph{length $|\cdot|$ of a cycle} as the number of production rules in the cycle.
\end{definition}
\begin{ex}
Both linear and non-linear cycles can lead to an infinite number of parse trees. For example, the rules $S\to S \mid \texttt{x}$ cause a linear cycle of length $|S\to S| = 1$, and generate only the string \texttt{x}. The same string can be generated by the rules  $S\to SS \mid \texttt{x} \mid \epsilon$, where the cycle $S\to SS$ is not linear.
\end{ex}

We can see that applying a non-linear cycle increases the length of the string. Therefore, a non-linear cycle can lead to an infinite number of parse trees all deriving the same string, only if some null rule (rule of the form $A\to\epsilon$) is also present in the grammar. It was shown in~\cite{etessami} that in such a case, a general exact algorithm for computing $P(\epsilon)$ does not exist. Moreover, we show (see~\ref{thm:p-epsilon-polynomial-zeros}) that the computation of $P(\epsilon)$ is at least as hard as finding the roots of polynomials over $\mathbb{R}$.

If we assume a probabilistic context-free grammar without null rules, the standard technique for calculating $ P(w) $ for a given grammar $ G $ is to transform G to its Chomsky-normal form (CNF). We can then apply the well-known dynamic programming parser Cocke-Kasami-Younger (CKY)~\cite{sipser2006}. While the latter was initially proposed for deterministic context-free grammar, its extensions for probabilistic CFGs are also available~\cite{chappelier1998}. The combination of CNF and CKY can calculate the probability of deriving arbitrary given $ w $ with any given grammar $ G $ (without null rules) in polynomial time.

In~\ref{app:removing-linear-cycles}, we propose a series of transformations that strips the linear cycles from a probabilistic context-free grammar, for which Eq.~\eqref{eq:p-word} will include a finite number of parse trees for any given string $w$. We show that such a transformation is applicable to any given PCFG. However, the transformed grammar is not paired with an efficient algorithm for enumerating the parse trees deriving a given string, as is the case for the combination of CNF and CKY.

\section{Expression-generating grammars}\label{sec:expression-generating-grammars}
We say a  $G$ grammar is \emph{expression-generating} if every word from its language unambiguously presents a mathematical expression. In the continuation of this article, we study a family of expression-generating context-free grammars. Let us first provide a simple example and then continue with defining \emph{expressions}.
\begin{ex}
    Consider a grammar $G=(\{S, M\}, \{\texttt{x}\}, S, R)$ with the rules
    $$
    \begin{array}{rcl}
         S & \to & S \texttt{+} M \mid M, \\
         M & \to & M\texttt{x} \mid \texttt{x}.
    \end{array}
    $$
Every string $w \in L(G)$ is of the form
$$
w = \underbrace{\texttt{x}\cdots\texttt{x}}_{k_1}
    \texttt{+} \underbrace{\texttt{x}\cdots\texttt{x}}_{k_2}
    \texttt{+} \cdots
    \texttt{+} \underbrace{\texttt{x}\cdots\texttt{x}}_{k_j}
$$
where $k_i\geq 1$. Thus, the strings in $L(G)$ correspond to polynomials $\sum \limits_{i=1}^{m} a_i x^i$ for some $m\in\mathbb{N}$ and $a_i\in \mathbb{N}_0$, where $\sum \limits_{i = 1}^m a_i > 0$.
\end{ex}

Expression-generating grammars are often used in equation discovery~\cite{todorovski1997, brence2021}, also known as symbolic regression. Symbolic regression study machine learning algorithms for training models that take a form of closed-form equations from data. The appropriate model is selected both in terms of accuracy on training data and its simplicity.

Most equation discovery algorithms follow a general generate-and-test paradigm for training the model. In the first (generate) phase, the algorithm generates expressions, following some generative model. The latter is often a stochastic process. In evolutionary approaches to equation discovery~\cite{schmidt2009}, the expressions are generated following their fitness, i.e., degree of fit to the training data. In grammar-based approaches~\cite{brence2021}, PCFG is used to generate expressions, where PCFG can specify various aspects of inductive bias: the space of expressions considered~\cite{todorovski1997} and the preference towards simpler equations~\cite{brence2021}.

In the second (test) phase, the algorithm estimates the degree of fit of the generated expression to the training data. It also often takes care of fitting the values of free constants in the expression to data. For example, rather than generating \texttt{2 x\textsubscript{1} + 3 x\textsubscript{2}} and \texttt{3 x\textsubscript{1} + 4 x\textsubscript{2}}, one can use a PCFG that generates the string \texttt{c x\textsubscript{1} + c x\textsubscript{2}}, where \texttt{c} is a symbol denoting a generic free constant. After the expression is generated, it is post-processed, so that the $i$-th occurrence of the symbol \texttt{c} is replaced by \texttt{c\textsubscript{i}}. Following the example above, we obtain the final string \texttt{c\textsubscript{1} x\textsubscript{1} + c\textsubscript{2} x\textsubscript{2}}. Finally, the expression is input to the constant-fitting algorithm that finds the value for each of the constants that leads to maximal fit with the training data.

 \begin{ex}
     Observe a data set, sampled from the equation $y = 2.5 x_1 - x_2$:
\begin{center}
    \begin{tabular}{rr|r}
    $x_1$ & $x_2$ & $y$ \\
    \hline
1  & 4 & -1.5\\
2  & 7 & -2.0\\
1  & -8 & 10.5\\
6  & -10 & 25.0
\end{tabular}
\end{center}
Suppose that the expression \texttt{c x\textsubscript{1}\textsuperscript{2} + c} is generated in the first try. After post-processing (\texttt{c\textsubscript{1} x\textsubscript{1}\textsuperscript{2} + c\textsubscript{2}}) and fitting the constants, we obtain the final equation $y = 0.65 x_1^2 + 1.2$ (if least-squares are used for fitting). In the second try, suppose the expression \texttt{c x\textsubscript{1} + c x\textsubscript{2}} is generated.
Then, it is post-processed to \texttt{c\textsubscript{1} x\textsubscript{1} + c\textsubscript{2} x\textsubscript{2}} and fitted to $y = 2.5 x_1 - 1.0 x_2$.

\end{ex}
Given a PCFG $G$, we want to compute the probability of generating a string that corresponds to a given expression $w$, taking into account all the strings in $L(G)$ that correspond to expressions that are equivalent to $w$. This is different from computing the probability of a $w$ as a string. For example, the strings \texttt{c x} and \texttt{c x + c x} are different, but the corresponding families of functions $\{x\mapsto c_1 x \mid c_1\in \mathbb{R} \}$ and $\{x\mapsto c_1 x_1 + c_2 x_2 \mid c_1, c_2\in\mathbb{R}\}$ are the same. More formally:

\begin{definition}
    Let $G$ be an equation generating PCFG. Suppose the set of terminals $T$ contains the symbols \texttt{x\textsubscript{1}}, \dots, \texttt{x\textsubscript{n}} that correspond to variables $x_1$, \dots, $x_n$. Let $D$ be their domain, and $\mathbb{F}$ be the domain for the free constants. Every string $w\in L(G)$ can we written as $w = w_1 \texttt{c} w_2 \texttt{c} \cdots w_{m} \texttt{c} w_{m + 1}$ for some $m\in\mathbb{N}_0$, where $\texttt{c} \notin w_i$, for $1\leq i\leq m + 1$. Given such a string and some values $c_1,\dots, c_m\in\mathbb{F}$, we define a function $f_{w, c_1, \dots, c_{m}}$ as

    \begin{align*}
        f_{w, c_1, \dots, c_{m }} &:\quad D_{w, c_1, \dots, c_{m }} &\to&&  K_{w, c_1, \dots, c_{m }}\hphantom{oooooooo} \\
        f_{w, c_1, \dots, c_{m }} &:\quad (x_1, \dots, x_n) & \mapsto && w_1 c_1 w_2 c_2 \dotsm w_m c_{m } w_{m + 1},
    \end{align*}
    where the occurrences of \texttt{x\textsubscript{i}} on the right-hand side are replaced by $x_i$, $1\leq i\leq n$, the domain $D_{w, c_1,\dots c_{m}}$ is the largest possible (possibly empty) and $K_{w, c_1,\dots, c_{m }}$ equals the $f_{w, c_1, \dots, c_{m }}$-image of $D_{w, c_1, \dots, c_{m }}$.
    Let $\mathcal{F}$ be the set of all such functions.
    We define mapping $\Phi\colon L(G) \to 2^\mathcal{F}$ that maps $w\in L(G)$ to the set of functions
    \begin{align*}
        \Phi(w) = \{f_{w, c_1, \dots, c_{m }} \mid c_1, \dotsc, c_m \in \mathbb{F} \}
    \end{align*}
    that can be obtained from $w$ using different values for $m$ constants that appear in $w$. We define an equivalence relation $\sim$ on $L(G)$ as
    $$
        w \sim v \Leftrightarrow \Phi(w) = \Phi(v).
    $$
    We define \emph{expressions} as the equivalence classes of the relation (elements of $L(G)/_\sim$) and denote them with $[w] = \{v \in L(G) \mid v \sim w\}$, $w \in L(G)$.
\end{definition}

The central aim of the next section of the article is to establish a general algorithm for calculating $P([w])$ for a given string $w$ and an expression-generating grammar $G$.

\section{Probability of generating an expression}
Let $G$ be an expression-generating grammar and $w \in L(G)$. We need an algorithm that calculates the probability of deriving any string $v$ that corresponds to an expression $[w]$, i.e.,
$$
P([w]) = \sum \limits_{v \sim w} P(v).
$$
From now on, we will use the short phrase ``deriving an expression $[w]$'' to replace the correct long version of ``deriving any string $v \sim w$ or $v \in [w]$''.

Let us first prove that the problem of calculating the probability is undecidable in general case, where an arbitrary expression-generating grammar can be provided at input. We can prove this by introducing an extension of a standard universal grammar for generating algebraic expressions, see, e.g.,~\cite{sipser2006}. Following the pattern of the universal grammar, the production rules for the starting non-terminal $E$ build sums of arbitrary number of factors $F$, non-terminal $F$ builds factors using multiplication and division of terms $T$. Terms $T$ can be simple variables $V$, generic (free) constants or constants with known values (e.g., $\pi$ or $\ln 2$) $C$, elementary functions of an expression $E$ gathered around the non-terminal $R$, and a simple bracketed expression $(E)$:
\begin{align*}
    E &\to \opcija{E \texttt{+} F}{p_{+}} \quad\mid\quad \opcija{E \texttt{-} F}{p_{-}} \quad\mid\quad \opcija{F}{1 - (p_{+} + p_{-})} \\
    F &\to \opcija{F \cdot T}{p_{\cdot}} \quad\mid\quad \opcija{F \texttt{/} T}{p_{/}} \quad\mid\quad \opcija{T}{1 - (p_{\cdot} + p_{/})} \\
    T &\to \opcija{\texttt{(}E\texttt{)}}{p_E} \quad\mid\quad \opcija{R}{p_R} \quad\mid\quad \opcija{V}{p_V} \quad\mid\quad \opcija{C}{1 - (p_E + p_R + p_V)} \\
    R &\to \opcija{\texttt{sin(}E\texttt{)}}{p_{\sin}} \quad\mid\quad \opcija{\texttt{exp(}E\texttt{)}}{p_{\exp}} \quad\mid\quad \opcija{\texttt{|}E\texttt{|}}{1 - (p_{\sin} + p_{\exp})} \\
    V &\to \opcija{\texttt{x}}{1} \\
    C &\to \opcija{\pi}{p_{\pi}} \quad\mid\quad \opcija{\ln 2}{p_{\ln}} \quad\mid\quad \opcija{Q}{p_Q} \quad\mid\quad \opcija{(\texttt{-}Q)}{1 - p_{\pi} - p_{\ln} - p_Q} \\
    Q &\to \opcija{\texttt{(}N\texttt{)} \texttt{/} \texttt{(}N \texttt{+} 1\texttt{)}}{1} \\
    N &\to \opcija{N \texttt{+} 1}{p_N} \quad\mid\quad \opcija{0}{1 - p_N}
\end{align*}

The selection of grammar rules corresponding to $R$ (elementary functions) and $C$ (constants, leading also to $Q$ and $N$) are aligned with the expressions in the Richardson's theorem used below to establish the undecidability of the general problem of calculating the probability of a given expression.

\subsection{Undecidaility for an arbitrary grammar}
\label{section:undeciability}
We will show that no general algorithm exists that would return $P([w])$ for every given grammar. Our proof relies on Richardson's theorem from~\cite{richardson}.
\begin{thm}[Richardson]
    Let $L$ be a set of strings representing $\mathbb{R} \to \mathbb{R}$ functions, containing strings $x$ (which represent identity), $\sin x, e^x, \ln 2, \pi, |x|$ and a set of rational numbers. Suppose that the set of functions represented by the strings in $L$ is closed under pointwise addition, subtraction, multiplication and composition. Then the problem of deciding, whenever a given string from $L$ represents a function, that is zero everywhere, is undecidable.
\end{thm}
It is now easy to prove undecidability of calculation of $P([w])$.
\begin{thm}
    \label{thm:undeciability}
    There is no general algorithm, that would take a grammar $G = (N, T, S, R)$ and a string $w \in T^*$, and would return the probability $P([w])$ of deriving an expression $[w]$.
\end{thm}
\begin{proof}
    Suppose such an algorithm exists for a grammar whose language $L(G)$ are strings corresponding to the functions that satisfy the assumptions of Richardson's theorem. For any $w\in L(G)$, we construct a probabilistic grammar $G_w = (\{S\}, T, S, R)$ with two rules
    $$
         S \to \opcija{0}{0.5} \mid \opcija{v}{0.5}.
    $$
    Note that string $v$ represents a function that is zero everywhere, if and only if $P([v]) = 1$. Thus, if we are able to calculate the probability $P([v])$ for all $v\in L(G)$, we obtain an algorithm, that contradicts Richardson's theorem. Therefore, a general algorithm for computing $P([w])$ does not exist.
\end{proof}

In the rest of this section, we focus on families of grammars, often used for equation discovery, for which such an algorithm exists, which is proved by computing the corresponding probabilities explicitly.

\subsection{Linear grammar}
\label{linear-grammar}
Observe a grammar with start symbol $E$, the set of terminal symbols $T = \{\texttt{c}, \texttt{+}, \texttt{x\textsubscript{1}}, \dotsc , \texttt{x\textsubscript{n}}\}$ and production rules
$$
\begin{array}{rcl}
    E & \to & \opcija{E \, \texttt{+} \, \texttt{c}V}{p} \mid \opcija{\texttt{c}}{1 -p}\\
    V & \to & \opcija{\texttt{x\textsubscript{1}}}{q_1} \mid \dotsb \mid \opcija{\texttt{x\textsubscript{n}}}{q_n}.
\end{array}
$$
Strings derived from this grammar take the form \texttt{c + c x\textsubscript{r\textsubscript{1}} + $\cdots$ + c x\textsubscript{r\textsubscript{k}}}, where $r_i \in \{1, \dotsc , n\}$. We are interested in $P([c +cx_{r_1} + \dotsb + cx_{r_k}])$.

\subsubsection{Exact formula}
We start with the easiest case of $n = 1$. If we use $E\to \texttt{c}$ at the beginning of the derivation, we will derive $\texttt{c}$. Otherwise, we rewrite $E\to E\; \texttt{+ c} V \to E\; \texttt{+ c x\textsubscript{1}}$, and continue recursively with rewriting $E$. Thus, the parse trees $\tau_i$, $i\geq 0$ derived with the grammar can be recursively defined as
\begin{center}
   \begin{tblr}{c c c c}
     $\tau_0 =$ &
     \begin{forest} [$E$ [\texttt{c}]]] \end{forest} &
     \hphantom{SSS} and\hphantom{SSS} $\tau_{i + 1} =$ &
        \begin{forest}
         [$E$
         [$\tau_i$]
         [\texttt{+}]
         [\texttt{c}]
         [$V$ [\texttt{x\textsubscript{1}}]]
         ]
        \end{forest}
\end{tblr}
\end{center}
with the probability of parsing $\tau_i$ being equal to $(p q_1)^i (1-p)$, where $i$ is also the number of occurrences of symbol \texttt{x\textsubscript{1}} in the string.
Thus, every tree corresponds to a different string. Since $q_1 = 1$, we have
$$
P([c+cx_1]) = \sum \limits_{i=1}^\infty (1-p)p^i = (1-p)\frac{p}{1-p} = p.
$$
Since $P([c]) + P([c + cx_1]) = 1$, we also proved that the process of production terminates with probability $1$.

We can derive a formula for $n > 1$ using the inclusion-exclusion principle. Consider a string $w = \texttt{c + c x\textsubscript{r\textsubscript{1}} + $\cdots$ + c x\textsubscript{r\textsubscript{k}}} \in L(G)$, where $1\leq r_1 < \dotsb < r_k \leq n$. Observe that a given string is an element of $[w]$ if and only if it contains at least one symbol \texttt{x\textsubscript{i}} precisely when $i \in \{r_1, \dotsc, r_k\}$.
We define $U=\{v \in L(G) \mid \forall j \in \{1, \dotsc , n\}\setminus \{r_1, \dotsc, r_k\}.\; \texttt{x\textsubscript{j}} \notin v\}$. An expression $[w]$ can now be written as
$$
[w] = \bigcap \limits_{i=1}^k \{v \in U \mid \texttt{x\textsubscript{r\textsubscript{i}}} \in v\}.
$$
The set $U$ is a disjoint union of  a set $[w]$ and a set
$$[w]^c := \bigcup \limits_{i=1}^k\{ v \in U \mid \texttt{x\textsubscript{r\textsubscript{i}}} \notin v\}.$$
Therefore  $P([w]) = P(U) - P([w]^c)$.

Let  $p_i$ denote the sum of probabilities of parsing all the words from $U$, which contain at most $i$ symbols \texttt{+}.
Clearly, $\lim \limits_{i \to \infty}p_i = P(U)$ and $p_0= 1 - p$.
We derive a recursive formula for $p_i$. Every tree, which derives a string from $U$ and contains between $1$ and $i+1$ symbols $+$, $i \geq 0$, has the rule $E \to E\texttt{ + c}V$ in the root node. Then, the left subtree of the root node starts with $E$ and derives a word from $U$ with at most $i$ occurrences of symbol \texttt{+}. The probability of such subtree is $p_i$. The right subtree that starts with $V$ can be rewritten to one of the symbols from  $\{\texttt{x\textsubscript{r\textsubscript{1}}}, \dots, \texttt{x\textsubscript{r\textsubscript{k}}}\}$. This happens with the probability $\sum \limits_{j=1}^k q_{r_j}$. Therefore,
$$
p_{i+1} = (1 - p) + pp_i \sum \limits_{j=1}^k q_{r_j},
$$
and, in the limit, $P(U) = (1 - p) + p P(U) \sum \limits_{j=1}^k q_{r_j}$, so
$$P(U) =\displaystyle \frac{1-p}{1 -p \sum \limits_{j=1}^k q_{r_j}}.$$
We get $P([w]^c)$ with inclusion-exclusion principle as
$$
P(\bigcup \limits_{i=1}^k\{ v \in U \mid \texttt{x\textsubscript{r\textsubscript{i}}} \notin v\}) =
\sum \limits_{\emptyset \neq I \subseteq \{1, \dotsc, k\}} (-1)^{|I| + 1} P(A_I),
$$
where $A_I = \bigcap \limits_{i \in I} \{v \in U \mid \texttt{x\textsubscript{r\textsubscript{i}}} \notin v \}$. The derivation of the formula for $P(A_I)$ is similar to the derivation of the formula for $P(U)$ described above. Let $p_i'$ be the probability of parsing a word from $[w]^c$, which contains at most $i$ symbols $+$. Then $P(A) = \lim \limits_{i\to \infty} p_i'$ and (as derived above)
$$
p_{i+1}' = (1-p) + pp_i'\sum \limits_{j \in \{1, \dotsc, k\} \setminus I}q_{r_j},
$$
from which  $P(A_I) = \displaystyle \frac{1-p}{1-p\sum \limits_{i \in \{1, \dotsc, k\} \setminus I}q_{r_i}}$ follows.
Therefore
\begin{equation}
    \label{eq:linearna}
    P([w]) = \sum \limits_{I \subseteq \{1, \dotsc, k\}} (-1)^{|I|} \displaystyle \frac{1-p}{1-p\sum \limits_{i \in \{1, \dotsc, k\} \setminus I}q_{r_i}}.
\end{equation}
For the calculation of the sum \eqref{eq:linearna}, we need
$$
 \sum \limits_{I \subseteq \{1, \dotsc, k\}}  ( |\{1, \dotsc, k\} \setminus I| + 5) = \sum \limits_{i=0}^k  \binom{k}{i}(i+ 5) = 2^{k-1} (10 + k)
$$
elementary computing operations, where $k$ is the number of different variables  $x_i$ in the string $w$. This leads to an exponential time complexity with respect to $k$. For practical use of the formula, we need an efficient approximation of the exact formula.

\subsubsection{Approximation of the exact formula}

Let $w$ be as above a string that contains the symbols \texttt{x\textsubscript{r\textsubscript{1}}}, \dots \texttt{x\textsubscript{r\textsubscript{k}}}, and no other symbols \texttt{x\textsubscript{j}}.
Let $v \in [w]$ be a string with $i$ occurrences of a symbol \texttt{+} and let $l_j$ be the number of occurrences of a symbol \texttt{x\textsubscript{r\textsubscript{j}}} in the string $v$. Clearly, $l_1 + \dotsb + l_k = i$ and $l_j \geq 1$. For each such valid tuple $(l_1, \dotsc, l_k)$, there exist
$\binom{i}{l_1,\, \dotsc,\, l_k}$ different strings in $[w]$, which fulfill the upper demands. Since the probability of parsing  one such word is equal to $(1-p) p^i q_{r_1}^{l_1} \dotsm q_{r_k}^{l_k}$, the probability of parsing  $[w]$ is equal to
\begin{equation}
\label{eq:eq:linearna-vsota-neskoncna}
P([w])=
\sum \limits_{i= k}^\infty (1-p)p^i  \left ( \sum_{\substack{l_1 + \dotsb + l_k = i \\ l_j \geq 1}}\binom{i}{l_1, \dotsc, l_k} q_{r_1}^{l_1} \dotsm q_{r_k}^{l_k} \right )    .
\end{equation}
\begin{figure}[t]
\begin{subfigure}{0.49\textwidth}
    \centering
    \includegraphics[scale=0.25]{sum_elements_article4.png}

\end{subfigure}
\begin{subfigure}{0.49\textwidth}
    \centering
    \includegraphics[scale=0.25]{tloris.png}

\end{subfigure}
\caption{3D-bar plot (in two perspectives) of the sizes of the terms $\Tilde{\kappa}$ in the inner sum of Eq.~\eqref{eq:double-sum}, for $i = 15$, $k =3$, and $q_1 = q_2 = q_3 = 0.3$.}
\label{fig:multinomial_distribution}
\end{figure}

A good approximation for $P([w])$ would be
\begin{equation}
    \label{eq:double-sum}
\sum \limits_{i=k}^M (1-p)p^i  \left ( \sum_{\substack{l_1 + \dotsb + l_k = i \\ l_j \geq 1}}\kappa(l_1, \dotsc, l_k) \right )
\end{equation}
where
$$
\kappa(l_1, \dotsc, l_k) = \binom{i}{l_1, \dotsc, l_k} q_{r_1}^{l_1} \dotsm q_{r_k}^{l_k}
$$
and  $M\in \mathbb{N}$, but the calculation using this formula is still slow, due to the high number of terms in the inner sum -- for a given $i$, their number is $\binom{i-1}{k-1}$.
        Observe the  graphs  of $\Tilde{\kappa} \colon (l_1, \dotsc, l_{k-1}) \mapsto \kappa(l_1, \dotsc, l_{k-1}, i - \sum_{j = 1}^{k - 1} l_j)$ in Figure~\ref{fig:multinomial_distribution}. Clearly, $\kappa$ is a generalization of probability mass function of multinomial distribution, so there is (at least one) partition $p'= (l_1', \dotsc, l_{k-1}', l_k')$, $l_k' = i -\sum_{j = 1}^{k - 1} l_j'$, where $\Tilde{\kappa}$ reaches its maximum and the terms $\kappa(l_1, \dotsc, l_k)$ in the inner sum of Eq.~\eqref{eq:double-sum} decrease when the distance between $(l_1 , \dotsc, l_{k-1})$ and $(l_1' , \dotsc, l_{k-1}')$ increases. Therefore, the partitions that are far away from $p'$ can be ignored in the approximation.

\begin{figure}[t]
\begin{subfigure}{0.49\textwidth}
    \centering
    \includegraphics[width=\textwidth]{executions_log_cropped.pdf}
   \caption{Execution time (in seconds), for $p=0.5$.}
\end{subfigure}
\begin{subfigure}{0.49\textwidth}
    \centering
    \includegraphics[width=0.96\textwidth]{n_iter_time_log_cropped.pdf}
    \caption{Number of computed terms, for $k = 10$.}
\end{subfigure}
\caption{Computational complexity of the exact calculation and the approximation of the probability of the expression $c + c x_1 + \cdots + c x_{k}$ for the grammar with the rules
$E \to \opcija{E \, \texttt{+} \, \texttt{c}V}{p} \mid \opcija{\texttt{c}}{1 -p}$,
and
$V \to \opcija{\texttt{x\textsubscript{1}}}{q_1} \mid \dotsb \mid\opcija{\texttt{x\textsubscript{n}}}{q_k}$.
r different values of the desired accuracy $\epsilon$ and different numbers of variables $k$, where $q_1 = \dotsb = q_k = 1/k$. Graph (a) depicts the execution time (in seconds), and graph (b) depicts the number of iterations required to achieve the desired accuracy $\epsilon$.}
\label{graphs-time}
\end{figure}

We approximate each inner sum by starting with partitions that correspond to the (approximate) maximum of $\Tilde{\kappa}$ and moving to smaller elements using breadth-first search until enough elements are included to reach the desired precision. The number of iterations $M - k + 1$ and the number of ignored elements in each iteration can both be set to reach an approximation error smaller than $\epsilon$ for arbitrary given $\epsilon > 0$. \ref{apendix:izpeljava-aprox} provides implementation-level detailed description of the approximation algorithm. Let $\epsilon' = \epsilon / (2(M - k + 1))$ and $\overline{m}_k$ be the value of $\kappa(l_1, \dotsc, l_k)$ in the mode at $i = k$. As derived in \ref{apendix:aprox-complexity}, time complexity of the algorithm is bounded by
$$
T(M) \leq \mathcal{O}(M^2)\left( (M - k + 1) \binom{M}{k-1} - \frac{\epsilon'(1 - p^{M - 1 - k})}{(1 - p)^2 p^{M - 2} \overline{m}_k} \right).
$$

Figure~\ref{graphs-time} shows the utility of the approximation by showing the empirical comparison of the complexity of the exact algorithm to the approximate one for different values of $k$ and varying desired precision $\epsilon$. The comparison shows that for values of $k > 20 $, the approximate algorithm is significantly faster than the exact one.

\subsection{Polynomial grammar}
\label{polynomial-grammar}
Linear grammar from Section~\ref{linear-grammar} can be adapted to derive polynomials with constants. Instead of rewriting $V$ to a symbol for single variable, we rewrite it to a sequence of symbols that corresponds to a monomial $x_1^{m_1}\dotsb x_n^{m_n}$. Hence, we get the following \emph{polynomial grammar}, which generates polynomials  $c + cx_1^{m_{1, 1}}\dotsm x_n^{m_{n,1}} + \dotsb + cx_1^{m_{1, k}}\dotsm x_n^{m_{n,k}}$:
$$
\begin{array}{rcl}
    E & \to & \opcija{E \, \texttt{+} \, \texttt{c}V}{p} \mid \opcija{\texttt{c}}{1 -p}\\
    V & \to & \opcija{VF}{q} \mid \opcija{F}{1-q} \\
    F & \to & \opcija{\texttt{x\textsubscript{1}}}{q_1} \mid \dotsb \mid \opcija{\texttt{x\textsubscript{n}}}{q_n}.
\end{array}
$$
Note that $x_1^2 x_2$ cannot appear as a string in the language of this grammar, but only as an expression that corresponds to the strings \texttt{x\textsubscript{1}x\textsubscript{1}x\textsubscript{2}}, \texttt{x\textsubscript{1}x\textsubscript{2}x\textsubscript{1}} and \texttt{x\textsubscript{2}x\textsubscript{1}x\textsubscript{1}}. However, for readability, we abbreviate these strings as \texttt{x\textsubscript{1}\textsuperscript{2} x\textsubscript{2}}, and do similarly for the others in these section.

We now show that the computation of probability
$$
P([\texttt{c + c x\textsubscript{1}\textsuperscript{m\textsubscript{1,1}}} \cdots \texttt{x\textsubscript{n}\textsuperscript{m\textsubscript{n,1}}}
+ \dotsb +
\texttt{c x\textsubscript{1}\textsuperscript{m\textsubscript{1,k}}}\cdots \texttt{x\textsubscript{1}\textsuperscript{m\textsubscript{n,k}}}])
$$
for a given polynomial grammar can be translated to a problem of calculating the probability for a linear grammar. For start, note that every branch
$$
V \to VF \to VFF \to \dotsb \to VF\dotsm F \to FF\dotsb F \to
\texttt{x\textsubscript{r\textsubscript{1}}} \dotsb \texttt{x\textsubscript{r\textsubscript{k}}}$$
in the parse tree can be replaced with a single production rule $V \stackrel{p}{\to} x_1^{m_1}\cdots x_n^{m_n}$, where $x_1^{m_1}\cdots x_n^{m_n}$ should be understood as a single symbol and $p$ is the probability of generating the expression $x_1^{m_1}\cdots x_n^{m_n}$ from $V$ with a polynomial grammar. The resulting grammar is linear, so the procedure from Section~\ref{linear-grammar} can be applied to this grammar as well.

\begin{note}
The obtained structure is formally not a grammar, since it includes an infinite number of production rules for $V$, and an infinite number of terminals. However, for the purpose of computing the probabilities of expressions, we can allow any countable set of production rules and generalize the previous definitions (and procedures).
\end{note}

\noindent For a full algorithmic solution, the probability of deriving the expression $x_1^{m_1}\dotsm x_n^{m_n}$ from  $V$ must be calculated.
Let $M = m_1 + \dots + m_n$. To derive the expression from $V$, the rule $V\to VF$ must be applied $(M - 1)$-times and the rule $V\to F$ once. Then, each of the rules $F\to \texttt{x\textsubscript{i}}$ must be applied $m_i$ times. Thus, the probability of deriving the expression from  $V$ equals
$$
p = \binom{M}{m_1, \dotsc , m_n}q^{M-1}(1-q)q_1^{m_1}\dotsb q_n^{m_n}.
$$

\subsection{Rational grammar}
\label{rational-grammar}

Using the polynomial grammar from the previous section, we now define a grammar for deriving \emph{rational functions}. We introduce a new start symbol $S$ that is rewritten to the quotient $(E)/(E)$. Then, each $E$ is rewritten to an arbitrary polynomial:
$$
\begin{array}{rcl}
    S & \to & \opcija{(E) \texttt{/} (E)}{1}\\
    E & \to & \opcija{E\texttt{ + c}V}{p} \mid \opcija{\texttt{c}}{1 -p}\\
    V & \to & \opcija{VF}{q} \mid \opcija{F}{1-q}\\
    F & \to & \opcija{\texttt{x\textsubscript{1}}}{q_1} \mid \dotsb \mid \opcija{\texttt{x\textsubscript{n}}}{q_n}
\end{array}
$$
Strings $w$ derived by this grammar take the form of $u/v$ for any two strings $u$ and $v$ from the language of the polynomial grammar. To understand the structure of $[u/v]$, we use the following lemma.
\begin{lema}
\label{lema:racional-structure}
Let $u/v$ and $s/t$ be two strings from the language of the rational grammar, such that $u/v \sim s/t$. Than, $u \sim s$ and $v \sim t$.
\end{lema}
The immediate consequence of the lemma is that $P([u/v]) = P([u])P([v])$. The probabilities $P([u])$ and $P([v])$ can be calculated using the algorithm from Section~\ref{polynomial-grammar}.

\begin{proof}[Proof of Lemma \ref{lema:racional-structure}.]
First, we will prove $u \sim s$.
To do so, it is sufficient to prove that the same monomials occur in $u$ and $s$.

Let $N = x_1^{l_1}\dotsm  x_n^{l_n}$ be a monomial of the highest degree in $u$. We set the constant next to $N$ to $1$ while all the other free constants in $u$ are set to $0$.  In $v$ we set the free term (the constant next to the monomial $1$) to $1$, and all the other constants are set to $0$. This selection of constants in $u/v$ is equal to $N$ as a function, and since $u/v \sim s/t$, there exist a selection of constants $s'/t'$ for $s/t$ (where $s'$ is a polynomial obtained with a selection of constants in $s$, and $t'$ is a polynomial obtained with a selection of constants in $t$), such that $N$ is equal to $s' /t'$ (as a function).
Clearly, a degree  $\deg(s')$ must be equal to or larger than the degree $\deg (N)$. Since $N$ has the maximal degree in $u$, we have $\deg (s) \geq \deg(u)$. By a symmetric argument, we can prove that $\deg (u) \geq \deg(s)$, so the degrees of $u$ and $s$ are equal.

Let $u'' = N + \dotsb$ be a polynomial, which we get from a selection of constants in $u/v$, such that all the free constants in $u$ are set to $1$, the free term in $v$ is set to $1$, and all the other constants in $v$ are set to $0$. There exists selection of constants $s''$ in $s$ and $t''$ in $t$ that leads to $u'' = s'' / t''$, or
$$
s'' = t'' u'' = t'' (N + \dotsb),
$$
where $t''$ is not the zero polynomial.
As proved above, $\deg(s'') = \deg(N)$. Since $\deg(s'') = \deg(t'') + \deg(N)$, we have $\deg(t'') = 0$, i.e., $t''$ is a constant polynomial.
Since $s'' = t'' u''$, $s$ must include all the monomials from $u$. After appplying a symmetric argument, we prove that $s$ and $u$ contain the same monomials, so $u \sim s$. Following the same reasoning, we can prove $v \sim t$.
\end{proof}

\subsection{A note on alternative grammars for linear expressions}
The linear grammar, presented in section \ref{linear-grammar}, is used in algorithms such as~\cite{brence2021}, due to easy interpretation of probabilities $P(V  \to \texttt{x\textsubscript{i}})$. But any other grammar, that generates a subset of linear expressions with constants, could be used as well. Here, we present an alternative with a simpler formula for probabilities.
$$
\begin{array}{lcl}
    S & \to & \opcija{V_1 \texttt{ + c}}{p_0}\;\mid\; \opcija{\texttt{c}}{1 -p_0}\\
    V_1 & \to & \opcija{V_2 \texttt{ + c x\textsubscript{1}}}{p_1} \;\mid\; \opcija{V_2}{q_1} \;\mid\; \opcija{\texttt{c x\textsubscript{1}}}{1-p_1 - q_1} \\
    \vdots \\
    V_{n-1} & \to & \opcija{V_n \texttt{ + c x\textsubscript{n-1}}}{p_{n-1}} \;\mid\; \opcija{V_n}{q_{n-1}} \;\mid\; \opcija{\texttt{c x\textsubscript{n-1}}}{1-p_{n-1} - q_{n-1}} \\
    V_n  &\to & \opcija{\texttt{c x\textsubscript{n}}}{1}
\end{array}
$$
The equivalence classes $[w]$ for words $w$ of this grammar all contain only a single word (unlike the equivalence classes of the grammar from Section \ref{linear-grammar}). Thus, $P(w) = P([w])$ for any word $w$ and the probability of parsing the expression $[w] = c +cx_{r_1} + \dotsb + cx_{r_k}$ is equal to
$$
P([w]) =
\begin{cases}
    1 - p_0&;\; k = 0\\
    p_0\prod \limits_{i = 1}^{M }g(i)&;\; \text{otherwise}
\end{cases}\text{ ,\hphantom{ooooooiiooooo}}
$$
where  $M=\operatorname{max}(r_1, \dotsc, r_k)$ and
$$g(i)  =
    \begin{cases}
        p_i &  i \in \{r_1, \dotsc, r_k\} \setminus\{M\}  \\
        1-p_i-q_i &  r_i = M \\
        q_i &\text{otherwise}
    \end{cases}.
$$

\section{Conclusion}

The article focuses on expression-generating probabilistic context-free grammars used for symbolic regression. We define expressions as equivalence classes of strings derived by grammar. We show that the problem of calculating the probability of deriving the strings in an equivalence class is undecidable in the general case of universal grammar for algebraic expressions. We present an algorithm for calculating the probability of a given expression generated with a given grammar for linear, polynomial, and rational expressions. Finally, we show that the exact probability can be efficiently approximated to a specified precision.

Two venues for further research emerge. First, a relevant open question for symbolic regression is what would be a most general restriction of the »Richardson« universal grammar presented in Section~4 that would allow for an algorithmic solution for calculating the probability of a given expression. For example, designing such an algorithm for a grammar that generates arbitrary algebraic expressions with four standard operators and generic constants would benefit symbolic regression. Second, the presented results on expression-generating expressions can be generalized to grammars generating groups, which might prove helpful in developing generative models and machine learning methods for algebraic structures.

\section*{Acknowledgements}
The authors acknowledge the financial support of the Slovenian Research Agency via the research core funding No.~P2-0103 and No.~P1-0294 as well as project No.~N2-0128.

redpajama_set_name: RedPajamaArXiv


text:
Gunmen kill four at pipeline works in Nigeria's oil-rich Delta
Tife Owolabi
By Tife Owolabi
YENAGOA, Nigeria (Reuters) - Gunmen have killed four men who were involved in the maintenance on a pipeline owned by the Nigerian subsidiary of Italian oil giant Eni, a local security spokesman told Reuters.
The men, two workers, a driver and a security operative, died at a facility in Nembe, Bayelsa state, which feeds oil and gas to the Brass export terminal, Solomon Ogbere, a spokesman for the Nigerian Security and Civil Defence Corps, said.
"During a routine work some gunmen yesterday attacked some contract workers working on a repair work a Nembe axis of Obama flow station killing two contract workers and a driver," Ogbere said on Sunday, adding that one of his men was also killed and two others who sustained injuries are receiving treatment.
A spokesman for Agip, the local subsidiary of Eni, did not immediately comment on the attack.
The identity and motive of the attackers was not immediately clear. The Delta, which produces the bulk of Nigeria's oil but is chronically underdeveloped, has been plagued by pirates, politically motivated militants and a range of armed criminals.
Also in Nembe, a wellhead continued to spew oil and gas earlier this week, three weeks after it failed, polluting the surrounding area and angering local residents.
(Reporting by Tife Owolabi; Writing by Libby George; Editing by Alexander Smith)
Former Hawaii coach June Jones rejects offer to return
Former Hawaii football coach June Jones has declined a proposal to return to lead the program for a second time. The school's wins leader in Division I, Jones met Friday with the athletic director David Matlin, the Honolulu Star-Advertiser reported, and rejected the offer when he learned it would only be for two years and Matlin would have to approve the assistant coaches. Jones took to social media to voice his displeasure with the terms.
Thieves captured on video stealing from South Gate Ulta store
Footage captured a group of brazen thieves as they shoplifted in broad daylight from a South Gate Ulta Beauty store and walked out with bags filled with merchandise.
Protesters March Through DC During 'March for Life' Rally
Big crowds were seen in Washington on Friday, January 21, for the annual March for Life rally, the largest anti-abortion rights demonstration in the country.This footage, taken by Twitter user @_ssimpson_, shows a group of demonstrators carrying upside-down US flags and Patriot Front flags, while chanting "reclaim America!" The organization is designated a "white nationalist hate group" by the Southern Poverty Law Center."Tens of thousands" of protesters attend the rally on the anniversary of the Supreme Court's 1973 Roe v Wade ruling, which legalized abortion in all 50 states, according to the event's website.A case currently before the Supreme Court could potentially overturn the landmark decision.Multiple street closures were in the process of reopening as of Friday afternoon, according to the Metropolitan Police Department. Credit: @_ssimpson_ via Storyful
Daily statistical milestones: Dwight Howard moves past Nate Thurmond and more
Here's your daily recap of movements in the all-time lists for scoring, rebounds, assists, blocks, steals and three-pointers after yesterday's games. Dwight Howard No. 10 in rebounds now Moved ahead of Nate Thurmond with 14,468 rebounds. He's now ...
The Abilene Reporter-News
Cherry on Top: Emphatic slam finishes off Cooper boys basketball's win against Wylie
Jalen Cherry's two-handed slam put the finishing touches on the Cooper boys basketball team's 54-41 win against Wylie at Cougar Gym on Friday night.
Bucks County Courier Times
Ben Simmons trade could define Daryl Morey's tenure with the Sixers
The Sixers' Daryl Morey realizes what's at stake with the Ben Simmons trade. It'll be interesting to see how the situation plays out.
Watertown Public Opinion
Girls Basketball: Fourth-rated Rapid City Stevens opens weekend with win over Watertown
Fourth-rated Class AA Rapid City Stevens turned fast starts in each of the first three quarters into a 50-29 non-conference girls basketball win over Watertown on Friday night in the Civic Arena.
Boys Basketball: Stark, Norberg combine for 41 points in Watertown's win over Rapid City Stevens
Reese Stark and Drew Norberg combined for 41 points to propel Watertown to a 61-51 high school boys basketball win over Rapid City Stevens on Friday night in the Civic Arena.
Residents hope for assistance

redpajama_set_name: RedPajamaCommonCrawl


There were more delays caused by issues in the timing system on Thursday evening, but things stabilized a bit and the focus got back to the team battles at hand in Lynchburg.
Liberty took advantage of a Florida Gulf Coast to open a big team lead at the CCSA Swimming & Diving Championships.
Bradlee Ashby took down a nine-year-old National Record in the 100 IM on day 3 of the New Zealand SC Championships.
Emma Robinson notched a Pan Pac qualifying time in the 1500 free on the final day of the New Zealand Open.
Daniel Hunter won his 4th-straight 50 free title, while Michael Pickett broke another National Age Group Record on Wednesday.
The Eagles sped to a victory in the final event, sealing their victory in the meet.
Coming off a dual-meet loss to Northwestern, the FGCU swimming and diving team (3-2, 2-0 CCSA) hosts a mid-major showdown against Toledo (3-2, 1-1 MAC) onThursday, Dec. 21, at 11 a.m. at the FGCU Aquatics Center.
After one day of swimming between the women-only teams of Florida Gulf Coast University and Rutgers University, FGCU leads 101-66.
Hosting its annual Green-Blue Scrimmage, the FGCU women's swimming and diving team kicked off its season against each other on Saturday with the Blue Team winning, 226-205.
In the midst of another impressive fall season, the 26 FGCU swimming and diving team has added to its already highly-talented team with a pair of early signees as Izzi Clark and Rebecca Moynihan have signed their National Letters of Intent to join the Green and Blue in the fall of 2017.


Nourish and protect your hair with label.m Protein Spray. Enriched with a moisturising blend of jasmine, sweet pea, vanilla, wheat and soy, it also contains the innovative Enviroshield Complex which shields your hair from the damage caused by heat styling and UV rays. Your locks will be left feeling strong and healthy, whilst your colour will stay looking brighter for longer.


Thomas Kinkade, the so-called "Painter of Light," will present the worldwide TV unveiling of the fifth piece of 12 in his "Disney Dreams Collection" on ShopNBC Thursday.
The newest Studio Masterwork premieres at 8 p.m.
— "Snow White," "Pinocchio," and "Tinker Bell and Peter Pan" (K25558), images from the Disney Dreams Collection in gallery wrap canvas format.
— "Cinderella Wishes Upon a Dream" (K34614), the fourth piece in the Disney Dreams Collection in gallery wrap canvas format.
— "Cobblestone Bridge," "Cobblestone Brook," and "Cobblestone Lane" (K34670), The old-world romance of cobblestone paths brought to life with Kinkade's tranquil style.
— "Bridge of Hope" (K34776), custom framed and professionally matted print with certificate of authenticity.
Thomas Kinkade Co. publishes the work of Thomas Kinkade and distributes his art and related collectibles through independently owned galleries worldwide, an extensive network of branded and licensed dealers, and strategic marketing relationships with more than 70 licensees.
The company's primary products are canvas and paper reproductions that feature Kinkade's artistic unique use of light and his peaceful and inspiring themes. Kinkade, known as the "Painter of Light™," is the most collected living artist in U.S. history.
You are currently browsing the archives for the Thomas Kinkade category.


text:
Brazilian Journal of Veterinary Research and Animal Science
UNDEFINIED
Origin of the Brachial Plexus of the monkey Cebus apella
Adriana Rodrigues Ribeiro Universidade de São Paulo, Faculdade de Medicina Veterinária e Zootecnia, São Paulo, SP
Irvênia Luiza de Santis Prada Universidade de São Paulo, Faculdade de Medicina Veterinária e Zootecnia, São Paulo, SP
Zenon Silva Universidade Federal de Uberlândia, Instituto de Morfologia, Uberlândia, MG
Roseâmely Angélica de Carvalho Barros Universidade de São Paulo, Faculdade de Medicina Veterinária e Zootecnia, São Paulo, SP
Daniela Cristina de Oliveira Silva Universidade de São Paulo, Instituto de Ciências Biomédicas, São Paulo, SP
https://doi.org/10.11606/issn.1678-4456.bjvras.2005.26445
Cebidae, Monkey, Neuroanatomy, Brachial plexus, Primates
The monkey Cebus apella, native to South American forests, is geographically distributed through the Brazilian land and presents satisfactory adaptation to the captive life showing great capacity of reproduction. Thus, we have described the origin of the brachial plexus in the monkey Cebus apella. The aim of this study was to add information for morphofunctional and comparative studies focusing on Cebus apella, humans and domestic animals. Twenty adult animals, 10 males and 10 females, belonging to the collection of Anatomy Laboratory of the Federal University of Uberlândia were obtained and prepared through fixation and dissection. In the dissected specimens, the brachial plexus of Cebus apella was comprised of nerve roots from C5 to T1 (55,00 ±± 11,12%), from C5 to T2 (25,00 ±± 9,68%), from C4 to T1 (15,00 ±± 7,98%) and from C4 to T2 (5,00 ±± 4,87%). In addition, the occurrence of pre- and post- fixation of the plexus as well as its cranial and caudal extent have been discussed. In conclusion, the brachial plexus of Cebus apella is constituted by nerve roots from C5 to T1.
PDF (Português (Brasil))
Ribeiro, A. R., Prada, I. L. de S., Silva, Z., Barros, R. A. de C., & Silva, D. C. de O. (2005). Origin of the Brachial Plexus of the monkey Cebus apella. Brazilian Journal of Veterinary Research and Animal Science, 42(2), 143-149. https://doi.org/10.11606/issn.1678-4456.bjvras.2005.26445
The journal content is authorized under the Creative Commons BY-NC-SA license (summary of the license: https://creativecommons.org/licenses/by-nc-sa/4.0 | full text of the license: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode)
Mary Marcondes, Maria Lúcia Zaidan Dagli, Masao Iwasaki, Irvênia Luiza de Santis Prada, Congenital hydrocephalus in dog: revision of literature and report of a clinical case , Brazilian Journal of Veterinary Research and Animal Science: Vol. 29 No. 1 (1992)
Rosa Helena dos Santos Ferraz, Gilmar Rodrigues Lopes, Alan Peres Ferraz de Melo, Irvênia Luiza de Santis Prada, Anatomical study of the intrapelvic portion of ischiatic nerve in fetuses in crossbred zebu cattle , Brazilian Journal of Veterinary Research and Animal Science: Vol. 43 No. 3 (2006)
Celina Almeida Furlanetto Mançanares, Irvênia Luiza de Santis Prada, Ana Flávia de Carvalho, Maria Angélica Miglino, João Flávio Panattoni Martins, Carlos Eduardo Ambrósio, Morphology of the pineal gland in opossum (Didelphis sp) , Brazilian Journal of Veterinary Research and Animal Science: Vol. 44 No. 3 (2007)
Mariana Matera Veras, Maria Angélica Miglino, Zenon Silva, Morphology of the female reproductive tract of the brown howler monkey (Alouatta guariba clamitans) , Brazilian Journal of Veterinary Research and Animal Science: Vol. 44 No. 1 (2007)
Daiane dos Santos de Deus, Karime Cássia Silveira Gondim, Lázaro Antônio dos Santos, Daniela Cristina de Oliveira Silva, Lucas de Assis Ribeiro, Rodrigo Lopes de Felipe, Gustavo Alexandre de Oliveira Silva, Zenon Silva, Roseâmely Angélica de CARVALHO-BARROS, Comparative descriptive anatomy of the femoral artery in crab-eating fox, hoary fox and maned wolf , Brazilian Journal of Veterinary Research and Animal Science: Vol. 54 No. 3 (2017)
Karina do Valle Marques, Mariana Matera Veras, Zenon Silva, Flavia de Oliveira, Daniela Cristina O. Silva, Irvênia Luiza S. Prada, Edson A. Liberti, Analysis of the brainstem internal morphology of the capuchin monkey (Cebus apella) , Brazilian Journal of Veterinary Research and Animal Science: Vol. 47 No. 2 (2010)
Dulcinéa Gonçalves Teixeira, José Luiz Guerra, Zenon Silva, Rose Eli Grassi Rici Azarias, Maria Fátima Martins, Macroscopic aspects of the anatomy of the reproductive system of escargots: Achatina fulica and Achatina monochromatica , Brazilian Journal of Veterinary Research and Animal Science: Vol. 45 No. 5 (2008)
Alessandra Esteves, Irvênia Luiza de Santis Prada, Ana Flávia de Carvalho, Celina Furlanetto Mançanares, Maria Angélica Miglino, Ricardo Rosa, Marco Antônio Roqueto, Comparative analisys of neuron densities in cortical areas of different dogs breed , Brazilian Journal of Veterinary Research and Animal Science: Vol. 45 No. 3 (2008)
Carlos Gomes Ferreira, Irvênia Luiza de Santis Prada, The brain arterial circuit in swine (Sus scrofa domesticus Linnaeus, 1758), behaviour and formation , Brazilian Journal of Veterinary Research and Animal Science: Vol. 42 No. 1 (2005)
Maria Aparecida de Alcântara, Irvênia Luiza de Santis Prada, Arteries of the basis of the encephalon in dogs (Canis familiaris, Linnaeus, 1758). I. Anatomical study of sources and behaviour , Brazilian Journal of Veterinary Research and Animal Science: Vol. 33 No. 2 (1996)


Set in lush gardens close by the Hastings River Broadwater is the Village Resort. In your private lagoon, experience swimming and water sports of all kinds. While on the shores, the stylish bungalows are perfect for relaxing, barbecues, and enjoying warm tropical nights. To keep you busy, try out the all-weather tennis courts or the recreational clubhouse with indoor heated pool, sauna, spa and gym. Be sure to mingle with your fellow vacationers at the resort-hosted Meet & Greet on Tuesday morning!
Your vacation unit is an individual villa, featuring TV, telephone, washer, dryer, air-conditioning and full kitchen with dishwasher and microwave. All units are three bedroom, hosting six to eight guests, with 2 queen-size beds, 4 single beds and 2 bathrooms. Because the resort is located approximately 8 minutes from the Central Business District of Port Macquarie, a car is recommended to fully enjoy the area.
Mandatory Utility surcharge is 0.31 local currency. Cash or Credit is accepted. Per kilowatt. Usage can be checked with reception any time during your stay.
The Resort is located approximately 8 minutes from the central business district of Port Macquarie.
Should you require a cot, highchair or stair gate, please contact the resort at least 48 hours prior to your travel dates. Subject to availability.


Altuzarra - Altuzarra reimagines traditional tailoring in a contemporary light for SS19 and this white Ravello blazer is the enchanting result, first unveiled on the SS19 runway. It's crafted in Italy from stretch-cotton tweed to a slim-fitting single-breasted silhouetted which is layered with a buttoned wool-blend cardigan, then lined with coordinating cream satin to ensure a streamlined finish. Team it with a pencil skirt and strappy sandals for an evening occasion.


text:
Q: C printing the same thing twice how do i stop this code from printing the same things twice
./run has has
instead of it printing
The same arguments have been found has at 1, 2

it prints
The same arguments have been found has at 1, 2
The same arguments have been found has at 2, 1

#include <string.h>

int main(int argc, char *argv[])
{
    int r, k;

    printf("Command Line Arguments: ");
    for (r = 1; r < argc; r++)
    {
        printf("%s ", argv[r]);
    }

    printf("\n");

    for (r = 1; r < argc; r++)
    {
        for (k = 1; k < argc; k++)
        {
            if (r != k && strcmp(argv[r], argv[k]) == 0)
            {
                printf("The same arguments have been found %s at %d, %d\n", argv[r], r, k);
            }
        }
    }

    return 0;
}

A: Simple; don't compare an argument to another argument that has already been compared to everything.
Instead of this:
for (k = 1; k < argc; k++)

do this:
for (k = r+1; k < argc; k++)

A: You code has a bug first
you forgot
#include <stdio.h>

second, the only time it prints twice is when you input two same arguments because of your condition checking
if you input 1, 2, two different arguments
it should only print once

redpajama_set_name: RedPajamaStackExchange


text:
Q: Mongodb merging multiple rows base on computed condition on row value I have a sample data like this:
[
  { objectId: 1, user: 1, phones: [1, 2], emails: ['a'] },
  { objectId: 2, user: 1, phones: [1, 5], emails: ['a', 'f'] },
  { objectId: 3, user: 1, phones: [8, 9], emails: ['f', 'g'] },
  { objectId: 4, user: 1, phones: [10], emails: ['h'] },
  { objectId: 5, user: 2, phones: [1, 2, 3], emails: ['aa', 'bb', cc'] },
]

Now I need to merge all related rows into one on these conditions:

*

*Have same user

*Have at least either one common phone or email

So output something like this:
[
  { objectId: 1, user: 1, phones: [1, 2, 5, 8, 9], emails: ['a', 'f', 'g'] },
  { objectId: 4, user: 1, phones: [10], emails: ['h'] },
  { objectId: 5, user: 2, phones: [1, 2, 3], emails: ['aa', 'bb', cc'] },
]

This is what I have came up with so far:
[
  {
    $unwind: {
      path: "$phones",
      preserveNullAndEmptyArrays: true
    }
  },
  {
    $group: {
      _id: {
        user: "$user",
        phone: "$phones"
      },
      objectIds: {
        $addToSet: "$_id"
      },
      emailsList: {
        $push: "$emails"
      },
      user: { $first: "$user" },
      phones: {
        $first: "$phones"
      }
    }
  },
  {
    "$addFields": {
      "emails": {
        "$reduce": {
          "input": "$emailsList",
          "initialValue": [],
          "in": { "$setUnion": ["$$value", "$$this"] }
        }
      }
    }
  },

  {
    "$project": {
      "emailsList": 0
    }
  },
  {
    $unwind: {
      path: "$emails",
      preserveNullAndEmptyArrays: true
    }
  },
  {
    $group: {
      _id: {
        user: "$user",
        phone: "$emails"
      },
      objectIdsList: {
        $push: "$objectIds"
      }
    }
  },
  {
    "$project": {
      "mergedObjectIds": {
        "$reduce": {
          "input": "$objectIdsList",
          "initialValue": [],
          "in": { "$setUnion": ["$$value", "$$this"] }
        }
      }
    }
  }
]

And then we have a list of objectIds need to be merged in, then I will merge it all in application code. So is there anyway I can do that in aggregation framework alone, or pipe the result of this aggregate in to the next one

A: Unless I'm missing something, these are just the "sets" for each user. So simply unwind both arrays and accumulate via $addToSet for each of "phones" and "emails":
db.collection.aggregate([
  { "$unwind": "$phones" },
  { "$unwind": "$emails" },
  { "$group": {
    "_id": "$user",
    "phones": { "$addToSet": "$phones" },
    "emails": { "$addToSet": "$emails" }
  }}
])

Which returns:
{ "_id" : 2, "phones" : [ 3, 2, 1 ], "emails" : [ "cc", "bb", "aa" ] }
{ "_id" : 1, "phones" : [ 9, 1, 2, 5, 8 ], "emails" : [ "g", "f", "a" ] }

A "set" is not really considered to be "ordered", so if you expect a certain order then you need to sort elsewhere, and probably best in the client.
Any "unique" id's don't really apply here. If anything you would use a different accumulator like $min or $max, or maybe $first depending on what you want, however the only relevant details I see here is the "user" for grouping and the other accumulated "set" values.
Even though unwinding multiple arrays produces a "cartesian product" of the other values, it really does not matter when everything being pulled out is as "distinct" values anyway. This typically only matters where you need to "count" elements, and that is something your output is not looking for in the question.


text:
Free Intelligent Libraries
GDPR ONLINE LIBRARY
The General Data Protection Regulation (GDPR) is a regulation by which the European Parliament, the Council of the European Union and the European Commission intend to strengthen and unify data protection for all individuals within the European Union. Don't fall foul of this critically important regulation.
Data Security and GDPR
Asia Pacific +61 3 9079 2594
Europe & North America +44 20 3667 4866
contact@affinitext.com
By utilising this website, you accept the Terms of Use and the Cookie Policy for this website.
© 2023 Affinitext. All rights reserved.


text:
Hello Visitor!
Radical Right
Ruling Class
Christian fundis
Israel Lobby
Neocons
Paleo-cons
Petro-oligarchy
Bill Weinberg
Bethany Koval
Malka X
Nirit Ben Ari
Judith Mahoney Pasternak
Boycott Israel
Home » Blogs » Bill Weinberg
Bogus "anti-Zionism" deconstructed
blog | May 15, 2012 - 4:31pm | By Bill Weinberg
We have, of course, repeatedly pointed out that—however much Zionists may propagandistically abuse the charge—anti-Semitism (veiled, barely veiled, or plain old blatant) really is evidenced in much ostensibly "leftist" discourse these days. One alarmingly common fallacy probably falls into the "barely veiled" category: When "Zionism" is blamed for the ills of the global capitalist system, you know the writer is taking his cue from the Protocols—even if he is ostensibly coming from the "left." We most recently had to call out supporters of Venezuela's Hugo Chávez for engaging in this idiotic barbarism. Pointing this out is not a defense of Zionism.
Now, we wish we could have been at this event, instead of just getting it through the perhaps slightly distorted lens of The Forward of May 25. The YIVO Institute for Jewish Research held a conference at New York's Center for Jewish History entitled "Jews and the Left." Some of the speakers apparently touched on precisely the question of bogus anti-Zionism. Yet, we fear (or, actually, we hope) that The Forward is distorting their views. From the article:
One of the most intriguing aspects of the conference was the extent to which the participants who self-identify with the left agreed with the view that it had indeed betrayed the Jewish state. Mitchell Cohen, professor of political science at Baruch College, established a distinction between anti-Zionism as legitimate protest of state actions and anti-Zionism as sublimated anti-Semitism, indicating that much of the current discourse falls into the latter category. Moishe Postone, professor of history at the University of Chicago, gave a Marxist critique of anti-Zionism, which, he explained, has become a "fetishized form of anti-capitalism," meaning that people attribute to Israel and Jews all the negative effects of capitalism. This, he made clear, is racism pure and simple, and a fundamental flaw in leftist theory and practice.
We certainly agree that that Zionism-is-to-blame-for-capitalism hogwash is "racism pure and simple." But we see it less as a "flaw in leftist theory and practice" than right-wing ideology creeping into the left, with contemporary "leftists" being too naive to notice. We haven't read the works of professors Cohen and Postone, but we hope they would dissent from The Forward's characterization of them as as agreeing that the left has "betrayed the Jewish state." By buying such hogwash, the left has betrayed rationalism, secularism, anti-racism and class analysis—all the things that the left has traditionally stood for. And things which are also fundamentally incompatible with the notion of a "Jewish state"! And the problem is not merely "state actions" (as if a "Jewish state"—that is, an explicitly ethno-supremacist state—could "act" benignly), but (yes) Zionism.
Bogus, evil, wacky "anti-Zionism" that masks (however crudely) anti-Semitism can only be truly opposed by a legitimate anti-Zionism, that understands what Zionism is: the ideology and program of Jewish colonization of historic Palestine. Otherwise, we just have a demoralizing contest between competing reactionary ideologies.
We will try to find time to bone up on the works of Cohen and Postone, and report back our findings here. Meanwhile, the esteemed professors are more than invited to weigh in...
Senior Ranter
Bill Weinberg is an award-winning 25-year veteran journalist in the fields of human rights, indigenous peoples, ecology and war. He is the author of Homage to Chiapas: The New Indigenous Struggles in Mexico, now available from Verso Books, and War on the Land: Ecology and Politics in Central America (Zed Books, 1991).
Anti-Zionism
Der Judenstaat
Homeland for the Jewish people
Hugo Ch
Mitchell Cohen
Moishe Postone
The YIVO Institute
Bill Weinberg's blog
Straw argument
by Anonymous | May 22, 2012 - 8:51am
This is an overstated, straw argument. It has little basis in fact within the broad contemporary Left. If Zionism is, as you state, a colonization project, it is also greatly informed historically by European colonial ideology, itself rooted in imperialist interests founded in the exigencies of capitalist expansionism. Zionism, colonialism, and capitalism are of course not the same thing (some early Zionists, for instance, claim to have been socialists--although they were also racist in their Eurocentric sense of superiority to indigenous Palestinians); however, these practices quickly became--and today remain--systemically intereffective. The pro-Israel lobby in the U.S. can neither be ignored nor denied, for prime example; to do so is itself antisemitic. Nor should one forget Theodor Herzl's support and recommendation for petit bourgeois settlement of Palestine as opposed to that backed by Rothschild or the "socialist" kibbutzniks. See the following article for a relevant analysis:
http://icmes.academia.edu/TerriGinsberg/Papers/1061518/The_Deployment_of...
Talk about "straw arguments"
by Bill Weinberg | June 1, 2012 - 11:45pm
How does any of that address what I said? Every word you wrote is irrelevant. Want to try again?
by Anonymous | May 17, 2012 - 10:14am
The problem is a small group of humans decided the larger group of humans make the most "wealth" accumulation in labor capital.
The small group of humans are not any "religion," but indeed, the yoke of religion is what has been used since the beginning of being able to brainwash, and this conditioning was advanced in Pavlov's experimentation, to enslave the masses of humans for the few humans that decided to be more "elite."
Fast forward and the digital computer keystroke "monies," was basically a shadow power orchestrated in systems which are obvious: education, information, medical, religious, government, et Cetera. Bio-metric gulags now we can prove in the NO privacy for any individual living in the U.S., and globally.
Who and whom are in charge? Herein lies the rub. We must, every human in the cognitive seeking to undo the dissonance, expose the digital computer faux wealth because the cannibals have not changed since first roaming the planet.
Once a cannibal, always it appears. Thus, the cannibal class must be at long last on earth, taken into healing centers to cycle the time necessary for higher intelligence to prevail over computer digital faux wealth.
Comment viewing options
Flat list - collapsedFlat list - expandedThreaded list - collapsedThreaded list - expanded
Date - newest firstDate - oldest first
10 comments per page30 comments per page50 comments per page70 comments per page90 comments per page150 comments per page200 comments per page250 comments per page300 comments per page
Select your preferred way to display the comments and click "Save settings" to activate your changes.
Anti-Semitic attacks in Bolivia: usual confusion (60.0%)
Anti-Zionism, anti-Semitism and 'bad facts' (60.0%)
Diaspora Jews feel Gaza backlash —again (60.0%)
Ikhwan Holocaust denial abets Zionists (60.0%)
France: Muslims under attack... and Jews (60.0%)
Powered by Phase2 Technology


This hands-on day will be led by curators from Museums Worcestershire and is designed to share practical skills. The session will support museum staff and volunteers working with historic costume and who are interested in learning more about handling, packing and caring for costume and textile collections.
Please note that places are limited for this event and that we will only accept one delegate per museum initially. Refreshments will be provided but delegates will need to bring their own packed lunch.
The event will run from 10am–4pm at Museums Worcestershire Collections Store, Hartlebury, Worcestershire.
This event is aimed at Accredited Museums and those officially Working Towards Accreditation in the West Midlands.


In September 2010 I visited the Gift of Sight Charity at Southampton General Hospital and met Professor Andrew Lotery who established the research centre in 2004 with the aim of funding world-class research into the prevention and treatment of blindness.
The Scooter Challenge was born!
As a teacher and a pub licensee I have led some amazing fund raisers for a variety of charities. Thirty Four years ago I just failed in my attempt to break the World Crawling Record and since then, along with others I have completed The London Marathon three times, The New York Marathon twice, The Paris Marathon twice, The Dublin Marathon and numerous Half Marathons and 10k's.
Other fund raising ideas have included Twenty Four Sports in 24 Hours, Maggot Racing, Snail Racing, Charity Cricket, Football and Rugby Matches and many many more.
I think, however, our next activity for the Southampton General Hospital based charity 'The Gift of Sight' is probably the most challenging to date.
I did not complete a run for charity in 2010 due to an injury to my right knee, so in an effort to find a sporting activity where one leg could remain comparatively still, I decided some form of journey on a child's style push scooter would be the answer, and where else to ride the scooter but from Lands' End to John O'Groats.
To my knowledge this is the first time this journey has been completed by scooter and we are starting the expedition in Lands'End on Sunday 27th Feb 2011, and will reach our destination John O'Groats on Saturday 5th March 2011.
The expedition will be a relay comprising of at least two teams of six, each team member will be required to 'scoot' for 3 x 4 mile 30 minute sessions, in a nine hour period before resting. In total we envisage each team member to complete stages totalling about 85 miles. The total distance for the chosen route is 1017 miles, if we don't get lost! We will be taking two minibus support vehicles and when not 'scooting' team members will share driving duties where possible. We will be staying in Cornwall on Sunday 27th Feb 2011, and starting from Lands' End at 8am Monday morning; we will scoot 24 hours a day. Our planned completion time will be noon on Saturday 5th March. We have hired 2 Motor Homes from Solent Motor Homes Ltd, who kindly hired them to us at a 'special' rate for the participants to sleep in on their break time. We are staying in Hayle on Sunday 27th Feb, setting off early on Monday 28th Feb. The Norseman Hotel, Wick is our final resting place next Saturday.


text:
One of India's most influential celebrity, motivational speaker and author
Chetan Bhagat is a renowned Indian youth icon, author, screenwriter, and columnist. Time magazine named him as one of the "100 Most Influential People in the World 2010", Fast company as one of the "100 most Creative People in Business 2011", Forbes India as one of the "Top 100 Celebrities of India 2012", and India Today included him in the "Power List 2013".
Bhagat is the author of five bestselling novels, 'Five Point Someone' (2004), 'One Night @ the Call Center' (2005), 'The 3 Mistakes of My Life' (2008), '2 States' (2009) & 'Revolution 2020: Love, Corruption, Ambition' (2011). All five books have remained bestsellers since their release and two have inspired Bollywood films (including the hit film 3 Idiots). In 2008, The New York Times called Bhagat "the biggest selling English language novelist in India's history". He has sold over 7 million books, which have been translated into 15 languages.
Bhagat also writes op-ed columns for English and Hindi newspapers, including The Guardian, The Times of India and Dainik Bhaskar, focusing on youth, career and issues based on national development.
He is a very popular motivational speaker and has spoken at more than 100 organisations in more than 75 cities around the world. He speaks at corporates, educational institutes, government bodies and volunteer agencies. He shares his thoughts and experiences on topics such as leadership, passion, values, team building, motivation, and achieving goals.
He had been working as an investment banker in Hong Kong for 11 years at Goldman Sachs and Deutsche Bank, before moving to Mumbai to pursue his passion for writing. Bhagat is an alumnus of Indian Institute of Technology (IIT) Delhi, and IIM Ahmedabad.
#Motivation
Former Prime Minister of Denmark ; CEO of Save the Children (2016-2019)
CEO National Institution for Transforming India
Paul Keating
Former Prime Minister of Australia
Rahul Bose
Indian actor, screenwriter, director, internationally recognised social activist, philanthropist and former Indian rugby union player
Tenzin P. Rinpoche
Founder and Director of the Dalai Lama Center for Ethics and Transformative Values at the Massachusetts Institute of Technology (MIT)
Lara Setrakian
Co-Founder of News Deeply and former Foreign Correspondent.
Mohammed Johmani
Founder of O2 Network
Marvin Zonis
Professor Emeritus, the University of Chicago, Booth School of Business
Sayeeda Warsi
Recent Co-Chair UK Conservative Party and first female Muslim to attend cabinet
Mick Cornett
Mayor of Oklahoma City (2004 - 2018)


text:
+61 3 6231 2999 mail@conferencedesign.com.auANZSN ASM 2017
Auxiliary Meetings
Auxiliary Meetings Information and Registration
Nephrology and Transplantation Update Course
Renal Dietitians Update Day Program
10th ANZSIN Meeting
Seminar Speakers
Update Course Speakers
ASM Awards & Prizes
Guidelines for Prize and Mini Oral Presenters
Guidelines for Displaying a Poster
Sponsor and Exhibitor Profiles
Exhibitors Manual
Dr Jaqui Hughes
Update Course Speaker
Dr Jaqui Hughes works as a nephrologist at Royal Darwin Hospital and NHMRC early career research fellow at Menzies School of Health Research. She is a Torres Strait Islander woman who grew up in Darwin before studying medicine at Newcastle University. She is a passionate clinician with a keen interest in Indigenous body composition and chronic disease prevention. She completed her PhD examining the body build and composition of Aboriginal and Torres Strait Islander people, and its relationship with obesity and chronic disease including diabetes and chronic kidney disease. She hopes this research will lead to more preventative management by identifying risk factors early and shifting the Indigenous health focus from treating the illness once its happens. She is also involved in collaborative research involving adults with chronic kidney disease (the eGFR Study, ME & Kidney Care study) and who require dialysis (the STARRS project, Perio-CKD Study, WICKD Study, AKI STudy).
Dr Hughes is an inspiration to others which was recognised by being awarded the 2012 Northern Territory (NT) Young Tall Poppy Award and the 2013 Top End (NT) NAIDOC Person of the Year. Her clinical-research group was also awarded the 2016 Harry Giese Research into Action Award for "Closing the loop on life-threatening melioidosis infections: observational research informing clinical practice change and policy for adults with severe kidney disease.
She is also the co-convenor of Australia and New Zealand Dialysis and Transplantation Registry (ANZDATA) Indigenous Working Group (2014-), an Expert Advisor for Indigenous Renal Disease, The Primary Care Education Advisory Committee for Kidney Health Australia (PEAK)(2014-), and former member of RACP Aboriginal and Torres Strait Islander Health Advisory Group (2008-2013).
Previous article Associate Professor Kevan Polkinghorne (BHB, MBChB, FRACP, MClinEpi, PhD)
Next article Kate Wyburn
About ANZSN
The ASM is hosted by Australian and New Zealand Society of Nephrology.
The aims of the Society are to promote and support the study of the kidney and urinary tract in health and disease, and to ensure the highest professional standards for the practice of nephrology in Australia and New Zealand.
https://www.nephrology.edu.au/
Please contact the team at Conference Design with any questions regarding the conference.
mail@conferencedesign.com.au
www.conferencedesign.com.au
/wp-content/uploads/2017/08/Conference-Design-400x400.png
© 2015 - 2016 Conference Design Pty Ltd


Computer Network Operations (CNO) is a broad term that has both military and civilian application. Conventional wisdom is that information is power, and more and more of the information necessary to make decisions is digitized and conveyed over an ever expanding network of computers and other electronic devices. Computer network operations are deliberate actions taken to leverage and optimize these networks to improve human endeavor and enterprise or, in warfare, to gain information superiority and deny the enemy this enabling capability.


SANTA CLARA — Mid-July no longer is too early to hype high school football. Players and coaches from 35 schools, most from the Bay Area, made their way onto a stage at Levi's Stadium on Wednesday to discuss their outlook for a season that starts in a little more than a month.
The headliner was the team that always garners the headlines, reigning state Open Division champion De La Salle-Concord.
A program well known for streaks, the Spartans still have a big one going as the new season approaches.
This fall will mark the 25th anniversary since De La Salle last lost to a Northern California opponent. Think about that: George H.W. Bush was still in the White House when DLS fell to Pittsburg 35-27 in a North Coast Section championship game Dec. 7, 1991.
Is that unbeaten run, which has included a few close calls and a couple of ties, still important for a program best known for a 151-game winning streak that stretched from 1992 to 2003?
"We have a lot of pride behind that," said Tre White, an all-section running back and defensive back.
DLS graduated most of its starters from a team that extended the program's run of consecutive NCS championships to 24 and won a second consecutive state title last fall. But this year's seniors sound plenty motivated to avoid any hiccups.
They remember being called the program's worst class in 25 years by an upperclassmen during morning announcements because they lost two freshman games.
Serra-San Mateo is one team eager for another crack at De La Salle. Postseason eligible again after a one-year ban by the Central Coast Section for forfeiting a consolation playoff game in 2014, the Padres will get their shot when they visit DLS on Sept. 2.
Nunn, the West Catholic Athletic League's player of the year last season, is also hungry for a return to the playoffs.
"It feels good that we can actually compete for a title," he said.
T.C. Lavulo, a running back and linebacker, said preparation for this season began as last season ended.
Sacred Heart Prep, the tiny private school from Atherton, has become a football power, with the likes of linebacker Ben Burr-Kirven, quarterback Mason Randall and tight end Andrew Daschbach leading the charge.
But the program is in new hands now, with Randall and Daschbach graduating from a team that won CCS and NorCal championships last season before losing in a state bowl game. Burr-Kirven graduated two years ago.
"I don't think you replace guys like Mason and Daschbach," coach Pete Lavorato said, noting that new quarterback Thomas Wine is a very good athlete. "We're going to adjust our offense a little bit, run a little more option. Maybe on pass-run situations, we'll have Thomas run the ball a little more than throw the ball like Mason last year.
Oak Grove-San Jose ended an eight-year CCS championship drought last season with a dramatic win over St. Francis-Mountain View in the Open Division II final.
The Eagles' best player from last year, running back Rashaan Fontenette, has moved on. But the team has added touted transfer Maurice Washington III from the The King's Academy-Sunnyvale.
Coach Jay Braun said he has not heard when Washington will be declared eligible by the CCS, but hopes it is in time for the season opener Aug. 26 at St. Francis.
Washington called Oak Grove his home school and that he wanted to come home.
New Palo Alto coach Danny Sullivan, a former quarterback at Los Gatos and Arizona State who spent the past few seasons as an assistant at Los Gatos, wasn't ready to reveal any tips when he and four of his players took their seats on the stage.
Quarterback Jordan Schilling said he has already learned a ton from Sullivan but conceded that he didn't know much about him before the hiring in the spring.
"I Google searched," Schilling said.
Campolindo-Moraga has become a little school that could under coach Kevin Macy, winning a state bowl game in 2014 and beating Milpitas, with its much larger enrollment, in a NorCal bowl game last season en route to playing in another state title game.
But the price of success is stronger competition.
Despite returning only three starters on defense and two on offense, Campolindo is now playing with the big boys — i.e. a league that includes Clayton Valley Charter, which beat Oak Grove in a NorCal bowl game last season.
Encinal-Alameda, with a list of alums that includes Jimmy Rollins and Dontrelle Willis, seems headed in an upward trend under third-year coach Ricky Rodriguez.
Winless two seasons ago, Encinal went 4-7 last year and is aiming for more wins this fall.
Rodriguez noted that his guys don't have the "high-profile rankings and are just kids that play football together their whole childhood. Our kids are very unique in the fact that to some of them football is all they've got.
Akil Francisco, a wide receiver and defensive back, has gone from not playing for the high school as a freshman to making a commitment to play for the University of Hawaii.
"He's an inspiration to this coaching staff as well," Rodriguez said.
The last NorCal program to beat De La Salle, tradition-rich Pittsburg, took the stage late in the day and was asked about its ultra-heavyweight Concord neighbor.
Is this the year to beat DLS?


text:
Oxford Research Encyclopedia of Natural Hazard Science
Oxford Research Encyclopedias Natural Hazard Science
Coastal Storm Surge
Convective Storms
Cultural Perspectives
Economic Analysis of Natural Hazards
Exposed Populations
Glacial Lake Outburst (GLOFs)
Policy and Governance
Population Movements
Risk Communication and Warnings
Winter Storms / Blizzards
Full Article (2)
Risk Assessment x
Climate Change x
Floods x
Adaptation x
Sort by Title - A to ZTitle - Z to AAuthor - A to ZAuthor - Z to APublished Online Date - Oldest FirstPublished Online Date - Newest First
Assessment and Adaptation to Climate Change-Related Flood Risks
Brenden Jongman, Hessel C. Winsemius, Stuart A. Fraser, Sanne Muis, and Philip J. Ward
The flooding of rivers and coastlines is the most frequent and damaging of all natural hazards. Between 1980 and 2016, total direct damages exceeded $1.6 trillion, and at least 225,000 people lost their lives. Recent events causing major economic losses include the 2011 river flooding in Thailand ($40 billion) and the 2013 coastal floods in the United States caused by Hurricane Sandy (over $50 billion). Flooding also triggers great humanitarian challenges. The 2015 Malawi floods were the worst in the country's history and were followed by food shortage across large parts of the country. Flood losses are increasing rapidly in some world regions, driven by economic development in floodplains and increases in the frequency of extreme precipitation events and global sea level due to climate change. The largest increase in flood losses is seen in low-income countries, where population growth is rapid and many cities are expanding quickly. At the same time, evidence shows that adaptation to flood risk is already happening, and a large proportion of losses can be contained successfully by effective risk management strategies. Such risk management strategies may include floodplain zoning, construction and maintenance of flood defenses, reforestation of land draining into rivers, and use of early warning systems. To reduce risk effectively, it is important to know the location and impact of potential floods under current and future social and environmental conditions. In a risk assessment, models can be used to map the flow of water over land after an intense rainfall event or storm surge (the hazard). Modeled for many different potential events, this provides estimates of potential inundation depth in flood-prone areas. Such maps can be constructed for various scenarios of climate change based on specific changes in rainfall, temperature, and sea level. To assess the impact of the modeled hazard (e.g., cost of damage or lives lost), the potential exposure (including buildings, population, and infrastructure) must be mapped using land-use and population density data and construction information. Population growth and urban expansion can be simulated by increasing the density or extent of the urban area in the model. The effects of floods on people and different types of buildings and infrastructure are determined using a vulnerability function. This indicates the damage expected to occur to a structure or group of people as a function of flood intensity (e.g., inundation depth and flow velocity). Potential adaptation measures such as land-use change or new flood defenses can be included in the model in order to understand how effective they may be in reducing flood risk. This way, risk assessments can demonstrate the possible approaches available to policymakers to build a less risky future.
Evolution of Strategic Flood Risk Management in Support of Social Justice, Ecosystem Health, and Resilience
Paul Sayers
Throughout history, flood management practice has evolved in response to flood events. This heuristic approach has yielded some important incremental shifts in both policy and planning (from the need to plan at a catchment scale to the recognition that flooding arises from multiple sources and that defenses, no matter how reliable, fail). Progress, however, has been painfully slow and sporadic, but a new, more strategic, approach is now emerging. A strategic approach does not, however, simply sustain an acceptable level of flood defence. Strategic Flood Risk Management (SFRM) is an approach that relies upon an adaptable portfolio of measures and policies to deliver outcomes that are socially just (when assessed against egalitarian, utilitarian, and Rawlsian principles), contribute positively to ecosystem services, and promote resilience. In doing so, SFRM offers a practical policy and planning framework to transform our understanding of risk and move toward a flood-resilient society. A strategic approach to flood management involves much more than simply reducing the chance of damage through the provision of "strong" structures and recognizes adaptive management as much more than simply "wait and see." SFRM is inherently risk based and implemented through a continuous process of review and adaptation that seeks to actively manage future uncertainty, a characteristic that sets it apart from the linear flood defense planning paradigm based upon a more certain view of the future. In doing so, SFRM accepts there is no silver bullet to flood issues and that people and economies cannot always be protected from flooding. It accepts flooding as an important ecosystem function and that a legitimate ecosystem service is its contribution to flood risk management. Perhaps most importantly, however, SFRM enables the inherent conflicts as well as opportunities that characterize flood management choices to be openly debated, priorities to be set, and difficult investment choices to be made.
Printed from Oxford Research Encyclopedias, Natural Hazard Science. Under the terms of the licence agreement, an individual user may print out a single article for personal use (for details see Privacy Policy and Legal Notice).