# Context-free Algorithms

Jonathan Graehl
SDL Research Work done at University of Southern California, Information
Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA 90292

(July 20, 2005)

###### Abstract

Algorithms on grammars/transducers with context-free derivations: hypergraph
reachability, shortest path, and inside-outside pruning of ’relatively
useless’ arcs that are unused by any near-shortest paths.

##  1 Introduction

We present algorithms on context-free grammars (and also on hypergraphs and
regular tree grammars, which share the same context-free derivation rule):
hypergraph reachability, shortest path, and inside-outside pruning of
’relatively useless’ arcs that are unused by any near-shortest paths. Section
2 is optional for those already familiar with regular tree grammars (analogous
to derivation trees of context free grammars) and/or hypergraphs.

##  2 Notation

###  2.1 Strings

$\Sigma^{\star}$ are the _strings over alphabet $\Sigma$_. For
$s=(s_{1},\ldots,s_{n})$ the _length_ of $s$ is $|s|\equiv n$ and the $i$_th
letter_ is $s[i]\equiv s_{i}$, for all $i\in
indices_{s}\equiv\\{i\in\mathbb{N}\;|\;1\leq i\leq n\\}$, and the
concatenation of a sequence of letters by index is
$s[({f}_{1},\ldots,{f}_{n})\in
indices_{s}^{\star}]\equiv(s[f[1]],\ldots,s[f[n]])$. _Concatenation_ of
strings is specified by the $\cdot$ operator, where $a\cdot
b\equiv(a[1],\ldots,a[|a|],b[1],\ldots,b[|b|])$.

###  2.2 Multisets

A _multiset $M$ of $S$_ is a partial function $M:S\rightarrow\mathbb{N}$, or
equivalently, a functional binary relation $M\subset S\times\mathbb{N}$. The
class of multisets of $S$ is written $\mathcal{M}(S)$. If
$M(s)=m\in{\mathbb{N}}$, we say $(x,m)\in{M}$, $x\in{M}$, and the
_multiplicity of $x$ in $M$_ is $m$. Intuitively, the multiplicity is the
number of times an element occurs. The _domain of $M$_ is $\text{dom
}M\equiv\\{x\in{M}\\}$. In some cases it is convenient to interpret $M$ as a
total function from $S\rightarrow(\mathbb{N}\cup\\{0\\})$ where
$M(x\notin{\text{dom }M})\equiv 0$. A set $S$ can be interpreted as a multiset
where each $x\in{S}$ has multiplicity $S(x)\equiv 1$. A sequence
$V=({v}_{1},\ldots,{v}_{n})\in{S^{\star}}$ can also be seen as a multiset with
$V(x)\equiv\sum_{i:v_{i}=x}1$ (after all, another notation of a multiset is
just a set listed without removal of duplicates, e.g. $\\{a,b,a\\}$).

###  2.3 Trees

$T_{\Sigma}$ is the set of _(rooted, ordered, labeled, finite) trees over
alphabet $\Sigma$._

$T_{\Sigma}(X)$ are the _trees over alphabet $\Sigma$, indexed by $X$_—the
subset of $T_{\Sigma\cup X}$ where only leaves may be labeled by $X$.
($T_{\Sigma}(\emptyset)=T_{\Sigma}$.) _Leaves_ are nodes with no children.

The _nodes_ of a tree _t_ are identified one-to-one with its _paths_ :
__$paths_{t}\subset
paths\equiv\mathbb{N}^{\star}\equiv\bigcup_{i=0}^{\infty}\mathbb{N}^{i}$
($A^{0}\equiv\\{()\\}$). The path to the root is the empty sequence $(),$ and
$p_{1}$ _extended by_ $p_{2}$ is $p_{1}\cdot p_{2}$, where $\cdot$ is
concatenation.

For $p\in{paths_{t}}$, $rank_{t}(p)$ is the number of children, or _rank_ , of
the node at $p$ in $t$, and $label_{t}(p)\in{\Sigma}\cup X$ is its _label_.
The _root of $t$_ is $root(t)=label_{t}(())$. The _ranked label_ of a node is
the pair $labelandrank_{t}(p)\equiv(label_{t}(p),rank_{t}(p))$. For $1\leq
i\leq rank_{t}(p)$, the $i$th _child_ of the node at $p$ is located at _path_
$p\cdot(i)$. The _subtree at path $p$ of $t$_ is $t\downarrow p$, defined by
$paths_{t\downarrow p}\equiv\\{q\;|\;p\cdot q\in{paths_{t}}\\}$ and
$labelandrank_{t\downarrow p}(q)\equiv labelandrank_{t}(p\cdot q)$. The
_children of $t$_ are $children_{t}\in T_{\Sigma}^{\star}$, with
$children_{t}[i]=t\downarrow(i),\forall 1\leq i\leq rank(t)$.

The _paths to $X$ in $t$_ are
$paths_{t}(X)\equiv\\{p\in{paths_{t}}\;|\;label_{t}(p)\in{X}\\}$. A _frontier_
is a set of paths $f$ that are _pairwise prefix-independent_ :

$\forall p_{1},p_{2}\in{f},p\in{paths}:p_{1}=p_{2}\cdot p\implies p_{1}=p_{2}$

A _frontier of t_ is a frontier $f\subseteq paths_{t}$.

For $t,s\in{T_{\Sigma}(X)},p\in{paths_{t}}$, $t[p\leftarrow s]$ is the
_substitution of $s$ for $p$_ in $t$, where the subtree at path $p$ is
replaced by $s$. For a frontier $f$ of $t$, the _mass substitution of $X$ for
the frontier $f$ in $t$_ is written $t[p\leftarrow X,\forall p\in{f}]$ and is
equivalent to substituting the $X(p)$ for the $p$ serially in any order.

The _yield of $X$ in_ $t$ is $yield_{t}(X)$, the string formed by reading out
the leaves labeled with $X$ in left-to-right order. The usual case (the _yield
of $t$_) is $yield_{t}\equiv yield_{t}(\Sigma)$.

We may also consider the _monadic strings_ in $t$,
$mstrings_{t}\subset\Sigma^{\star}$, obtained by reading off the labels along
some path from the root down. The paths that read off a monadic string $s$ in
$t$ are $mpaths_{t}^{{\approx}}(s)\equiv\\{p\in paths_{t}\;|\;\forall 1\leq
i\leq|p|+1:label_{t}(p\downarrow(1,i)){\approx}s[i]\\}$, and the string of
labels along a path is $mstring_{t}(p\in
paths_{t})\equiv\bullet_{i=1}^{|p|+1}(label_{t}(p\downarrow(1,i)))$ (so
$\forall p\in mpaths_{t}^{{\approx}}(s):mstring_{t}(p){\approx}s$). Then
$mstrings_{t}\equiv\\{mstring_{t}(p\in paths_{t})\\}$ and $t\downarrow s$ is
the sequence of _subtrees of $t$ along the monadic string $s$_ (in
lexicographic path order):

$t\downarrow^{{\approx}}s\in{mstrings_{t}}\equiv\bullet_{p\in
mpaths_{t}^{{\approx}}(s)\text{ in lexicographic order }}(t\downarrow p)$

Naturally, the path in $t$ to the $i$th element of $t\downarrow s$ is the
$i$th (in lexicographic order) $mpaths_{t}(s)$.

###  2.4 Regular Tree Grammars

A _weighted regular tree grammar_ (wRTG) $G$ is a quadruple $(\Sigma,N,S,P)$,
where $\Sigma$ is the alphabet, $N$ is the finite set of _nonterminals_ ,
$S\in{N}$ is the _start (or initial) nonterminal_ , and _$P\subseteq N\times
T_{\Sigma}(N)\times\mathbb{R}^{+}$_ is the finite set of _weighted
productions_ ($\mathbb{R}^{+}\equiv\\{r\in{\mathbb{R}}\;|\;r>0\\}$). We define
the binary relation $\Rightarrow_{G}$ (_single-step derives in G_) on
$T_{\Sigma}(N)\times(paths\times P)^{\star}$, pairs of trees and _derivation
histories_ , which are logs of (location, production used):

$\begin{array}[]{r}\Rightarrow_{G}\equiv\Bigl{\\{}((a,h),(b,h\cdot(p,(l,r,w)))\;\bigl{|}\\\
(l,r,w)\in{P}\wedge p\in{paths_{a}(\\{l\\})}\wedge b=a[p\leftarrow
r]\Bigl{\\}}\end{array}$

where $(a,h)\Rightarrow_{G}(b,h\cdot(p,(l,r,w)))$ iff tree $b$ may be derived
from tree $a$ by using the rule $l\rightarrow^{w}r$ to replace the nonterminal
leaf $l$ at path $p$ with $r$. For a derivation history
$h=((p_{1},(l_{1},r_{1},w_{1})),\ldots,(p_{n},(l_{1},r_{1},w_{1})))$, the
_weight of $h$_ is $w(h)\equiv\prod_{i=1}^{n}w_{i}$, and call $h$ _leftmost_
if $L(h)\equiv\forall 1\leq i<n:p_{i+1}\nless_{lex}p_{i}$.111$()<_{lex}(a)$,
$(a_{1})<_{lex}(a_{2})\textrm{ iff }a_{1}<a_{2}$, $(a_{1})\cdot
b_{1}<_{lex}(a_{2})\cdot b_{2}\textrm{ iff }a_{1}<a_{2}\vee(a_{1}=a_{2}\wedge
b_{1}<_{lex}b_{2})$

The reflexive, transitive closure of $\Rightarrow_{G}$ is written
$\Rightarrow_{G}^{\star}$ (_derives in $G$_), and the restriction of
$\Rightarrow_{G}^{\star}$ to leftmost derivation histories is
$\Rightarrow_{G}^{L*}$ (_leftmost derives in $G$_).

The _weight of $a$ becoming $b$ in $G$_ is
$w_{G}(a,b)\equiv\sum_{h:(a,())\Rightarrow_{G}^{L*}(b,h)}w(h)$, the sum of
weights of all unique (leftmost) derivations transforming $a$ to $b$, and the
_weight of $t$ in $G$_ is $W_{G}(t)=w_{G}(S,t)$. The _weighted regular tree
language produced by $G$_ is $L_{G}\equiv\\{(t,w)\in
T_{\Sigma}\times\mathbb{R}^{+}\;|\;W_{G}(t)=w\\}$.

The _derivation tree grammar_ for a wRTG $G=(\Sigma,N,S,P)$ is
$DG(G)=(P,N,S,P^{\prime})$, where

$P^{\prime}\equiv\\{(l,p(yield_{N}(r)),w)\;|\;p=(l,r,w)\in{P}\\}$

($p((s_{1},\ldots,s_{n})\in N^{\star})$ is the tree with root label $p$, rank
$n$, and ith child leaf $s_{i}$). The produced trees are called _derivation
trees_ and correspond one-to-one with tree-producing derivations in $G$.

###  2.5 Hypergraphs

A _(directed) hypergraph $G$_ is a pair $G=(V,E)$ where $V$ is a set of
_vertices_ (or _nodes_) of $G$, and $E$ are the _edges_ (or _hyperarcs_) of
$G$. An edge
$e=(h_{e}\in{V},T_{e},c_{e}:\mathbb{R}^{|T_{e}|}\rightarrow\mathbb{R})$ has
_head $h_{e}$_, _tails $T_{e}$_, and _cost function $c_{e}$_. The cost
function for an edge maps the costs of reaching its tails to the cost of
reaching the head through that edge.

In a hypergraph, $T_{e}\subseteq V$—the tails are subsets of the vertices.

In an _ordered multi-hypergraph_ , $T_{e}\in{V^{\star}}$—the tails are ordered
sequences.

Typically hyperarc cost functions are symmetric; if not, then the order of
arguments is the same as the order of tails. , or for unordered hypergraphs,
fixed by some arbitrary total order $<_{G}$ on $V$. The usual cost function is
given by $c_{e}({x}_{1},\ldots,{x}_{n})\equiv l_{e}+\sum_{i=1}^{n}x_{i}$,
where $l_{e}$ is the _length_ of the edge. A typical asymmetric cost function
would combine tail hyperpath costs with different weights for each tail.

We say there is a _hyperpath from $X\subseteq V$ to $y\in{V}$ in $G=(V,E)$_,
written $X\leadsto_{G}y$, if $y\in{X}\vee\exists e\in{E}:h_{e}=y\wedge\forall
t\in{T_{e}}:X\leadsto_{G}t$. A _hyperpath-tree $t\in{(X\leadsto_{G}y)}$_ is a
tree labeled by edges, corresponding to a proof of $X\leadsto_{G}y$ (with a
separate proof for each multiple occurrence of a tail vertex - note: the usual
B-hyperpath allows only a single incoming hyperarc/proof of each vertex - our
hyperpath-trees are more like derivations in a context-free grammar). The
_cost_ of a hyperpath-tree $p$ is written $c(p)$ and is computed bottom-up for
each subtree with root label $e$ using $c_{e}$.

For any derivation grammar $G^{\prime}=(P,N,S,P^{\prime})$ of wRTG
$G=(\Sigma,N,S,P)$, there is an equivalent ordered multi-hypergraph
$H=(N\cup\\{\omega\\},E)$ with an edge $e\in{E}$ for each production
$p=(l,r,w)\in{P^{\prime}}$ such that $h_{e}=l$,
$T_{e}=\left\\{\begin{array}[]{ll}{\\{\omega\\}}&\textit{if
}{yield_{N}(r)=\emptyset}\\\
{yield_{N}(r)}&\textit{otherwise}\end{array}\right.$, and the usual cost
function with $l_{e}=-\ln{w}$. The hyperpath-trees $\omega\leadsto_{H}S$ are
exactly the derivation trees for $G$, with the cost of the hyperpath-tree
equal to the $\ln$ of the weight of the tree (obviously, the labels of the
hyperpath-tree are $e\in{E}$ and the labels of the derivation tree are
$p\in{P}$, but there is an isomorphism between them, due to the construction
of $E$).

A hypergraph $(V,E)$ may be interpreted as a multigraph $(V,E^{\prime})$ with
an edge for every tail of each hyperarc ($E^{\prime}=\\{(h_{e},t\in
T_{e},c_{e})\;|\;(h_{e},T_{e},c_{e})\in E\\}$). We can refer to _simple_ (or
_monadic_) paths corresponding to the usual paths in the graph. In fact,
monadic strings $s$ of hyperarcs from a hyperpath-tree for $(V,E)$ correspond
to a simple path in $h_{s[|s|]}\leadsto_{(V,E^{\prime})}h_{s[1]}$.

##  3 Pruning Along a Hyperpath-Tree

If we are only interested in hyperpath-trees $X\leadsto_{G}y$, we can _prune
$G$ along $X$ to $y$_ by eliminating vertices and hyperarcs that don’t appear
in any (cheap) hyperpath-tree. This is analogous to the problem of reducing a
context free grammar by eliminating useless nonterminals [Hopcroft and
Ullman,, 1979], except that we wish to also eliminate those useful only for
high-cost hyperpath-trees.

Since we care only for the existence of a (cheapest) path for each node, tails
of edges may be considered as sets while addressing this problem, so that
multiply appearing tails $t$ in a multi-hypergraph always reuse the same
hyperpath-tree $X\leadsto_{G}t$. We assume the cost function
$c_{e}(c)=l_{e}+\sum_{(t,m)\in T_{e}}w_{e}(t)mc(t)$, where $c(t)$ is the cost
due to the hyperpath-tree $X\leadsto t$ and $w_{e}(t)$ is a weight given to
$t$-tails of that edge.

Unweighted pruning consists of first eliminating vertices (and hyperarcs they
occur in) that cannot be reached from the start, and second, eliminating from
the remainder all those that do not lie along any hyperpath-tree to the
destination. The first step can be performed in linear time by Algorithm 1.

Input:

A set of source nodes $X\subseteq V$ in a hypergraph $G=(V,E)$, nodes $V$, and
hyperarcs $E=\\{e_{1},\ldots,e_{m}\\}$ indexed by $1\leq i\leq m$. Each
hyperarc has tail nodes $T_{i}\subseteq V\equiv T_{e_{i}}$and head $h_{i}\in
V\equiv h_{e_{i}}$.

Output:

For all $y\in{V}$, $B[y]=\textbf{true}$ if $X\leadsto_{G}y$, false otherwise.
Time complexity is $O(t)$ where $t$ is the total size of the input.

begin

for  _$y\in{V}$_ do $B[y]\leftarrow\textbf{false}$

$\textit{Adj}[y]\leftarrow\\{\\}$

for  _$1\leq i\leq e$ , index of a hyperarc
$(T_{i}=\\{x_{1},\ldots,x_{k}\\})\rightarrow\\{h_{i}\\}$_ do

$r[i]\leftarrow k$

/* $r[i]$ is the number of tail nodes remaining before edge $i$ fires. */

for  _$1\leq j\leq k$_ do
$\textit{Adj}[x_{j}]\leftarrow\textit{Adj}[x_{j}]\cup\\{i\\}$

for  _$y\in X$_ do REACH(y)

$\textbf{REACH}(y)\equiv$ begin

if  _$\neg B[y]$_ then

$B[y]\leftarrow\textbf{true}$

for  _$i\in{\textit{Adj}[y]}$_ do

if  _$\neg B[h_{i}]$_ then

$r[i]\leftarrow r[i]-1$

if  _$r[i]=0$_ then $\textbf{REACH}(h_{i})$

Algorithm 1 Single-source-set hypergraph reachability

The weighted version of Algorithm 1 establishes the lowest cost way of
reaching each vertex from a start set (or that there is none). Algorithm 2,
adapted from [Knuth,, 1977] (first published in [Knight and Graehl,, 2005]),
is an extension of the graph shortest path problem [Dijkstra,, 1959] to the
hypergraph case. It works the same except that vertices are visited in
increasing order of the cost of reaching them from $X$, and so requires a
priority queue. Activated hyperarcs serve to potentially lower the cost of
reaching their head, but visiting the head is deferred until it is certain
that its minimal cost hyperpath-tree is known. This is in contrast to the
simple depth first approach in the unweighted case, where the head is visited
immediately with a recursive function call (using the implicit program stack
for queuing nodes).

Input:

A set of source nodes $X\subseteq V$ with initial costs $\\{i_{x},\forall
x\in{X}\\}$, and a hypergraph with $n$ nodes $V$, and $m$ hyperarcs
$({e}_{1},\ldots,{e}_{m})$ indexed by $1\leq i\leq m$. Each hyperarc has tail
nodes $T_{i}\subseteq V\equiv T_{e_{i}}$, head $h_{i}\in V\equiv h_{e_{i}}$,
and superior cost function $c_{i}\equiv c_{e_{i}}$ ($f$ is _superior_ iff
$f(x_{1},\ldots,x_{k})\geq x_{i},\forall 1\leq i\leq k$ [Knuth,, 1977]) of
variables $T_{i}$. The cost functions are implemented by constant time
operations BIND($c_{i},y\in T_{i},\text{cost of }y$) and INF($c_{i}$), which
returns a lower bound on the cost given the variables bound so far.

For a context-free grammar or regular tree grammar, introduce a fictitious
sink nonterminal $\omega$ to the rhs of terminal rules. Now let the $V$ be the
nonterminals, and let $X$ be ${\omega}$. For each ith rule, let $h_{i}$ be the
lhs nonterminal, $T_{i}$ be the set of rhs nonterminals (or ${\omega}$ if
there are none). Finally, initialize INF($c_{i}$) to
$w_{i}=-\log{P(i|h_{i})}$, the negative log rule probability of rule $i$, and
define BIND($c_{i},y\in T_{i},c$) as increasing INF($c_{i}$) by
${\\#}_{i}(y)c$, where ${\\#}_{i}(t)$ is the number of occurrences of
nonterminal $t$ in rule $i$.

Output:

For all $v\in{V}$, $\pi[v]=i$ is the index of the cheapest hyperarc with head
$h_{i}=v$, giving the predecessor relation of the cheapest unordered
hyperpath-tree from the $X\leadsto t$), and $\beta[v]$ is minimum cost of
reaching $v$. $\pi[v]=0$ if there is no cost-improving edge to $v$. Time
complexity is $O(n\lg{n}+t)$ where ($t$ is the total size of the input) if a
Fibonacci heap is used, or $O(m\lg{n}+t)$ if a binary heap is used.

begin

for  _$y\in{V}$_ do

if  _$y\in{X}$_ then $\beta[y]\leftarrow i_{y}$

else $\beta[y]\leftarrow\infty$

$\pi[y]\leftarrow 0$

$\textit{Adj}[y]\leftarrow\\{\\}$

$Q\leftarrow\textbf{HEAP-{CREATE}}()$

for  _$x\in{X}$_ do $\textbf{HEAP-{INSERT}}(Q,x,i_{x})$

for  _$1\leq i\leq m$ , index of a hyperarc
$(T_{i}=\\{x_{1},\ldots,x_{k}\\})\rightarrow^{c_{i}}\\{h_{i}\\}$_ do

$r[i]\leftarrow k$

/* $r[i]$ is the number of tail nodes remaining before edge $i$ fires. */

for  _$1\leq j\leq k$_ do
$\textit{Adj}[x_{j}]\leftarrow\textit{Adj}[x_{j}]\cup\\{i\\}$

while  _$Q\neq\emptyset$_ do

$y\leftarrow\textbf{HEAP-{EXTRACT-MIN}}(Q)$

for  _$i\in{\textit{Adj}[y]}$_ do

/* edge $i$ with $y$ as a tail */

if  _$\textbf{INF}(c_{i}) <\beta[h_{i}]$_ then

$\textbf{BIND}(c_{i},y,\beta[y])$

$r[i]\leftarrow r[i]-1$

if  _$r[i]=0$_ then

$c\leftarrow\textbf{INF}(c_{i})$

if  _$c <\beta[h_{i}]$_ then

if  _$\beta[h_{i}]=\infty$_ then $\textbf{HEAP-{INSERT}}(Q,h_{i},c)$

else $\textbf{HEAP-{DECREASE-KEY}}(Q,h_{i},c)$

$\pi[h_{i}]\leftarrow i$

$\beta[h_{i}]\leftarrow c$

Algorithm 2 ViterbiInside: single-source-set, multi-destination shortest
hyperpath-trees.

Having eliminated parts of the hypergraph that aren’t reachable from $X$, it
still remains to further remove any parts that don’t contribute to reaching
$y$. In Algorithm 3, we perform a simple depth-first traversal from heads to
tails of hyperarcs, starting with the destination $y$, ultimately saving only
vertices that can help reach $y$.

To see how this works, let the _restriction_ of hypergraph $G=(V,E)$ to a
subset of its vertices $V^{\prime}\subseteq V$ be
${{G}\langle{V^{\prime}}\rangle}\equiv(V^{\prime},E):E^{\prime}=\\{e\in
E\;|\;h_{e}\in V^{\prime}\wedge T_{e}\subseteq V^{\prime}\\}$. First, run
Algorithm 1 on $G$ to find $V^{\prime}=\\{v\in
V^{\prime}\;|\;X\leadsto_{G}\\}$, then second, run Algorithm 3 on the
resulting restriction $G^{\prime}={{G}\langle{V^{\prime}}\rangle}$ to find
$V^{\prime\prime}=\\{v\in V^{\prime}\;|\;\exists
F\supseteq\\{v\\}:F\leadsto_{G^{\prime}}y$. Then the hypergraph
$G^{\prime\prime}={{G^{\prime}}\langle{V^{\prime\prime}}\rangle}$ has the same
hyperpath-trees $X\leadsto_{G^{\prime\prime}}y$ as $G$, and is the minimal
such.

The order of these steps is essential - there may be vertices that only help
reach $y$ through hyperarcs that are eliminated in Algorithm 1. In the second
step, we qualify each node $t\in T_{e}$ that is connected through $e$ to $y$
as participating in a path to $X\leadsto_{G}h_{e}$ automatically, which is
sound only if we can assume some path from $X\leadsto_{G}t^{\prime}$, for all
$t^{\prime}\in T_{e}$. But the first step guarantees this by removing all
nodes that aren’t reachable from $X$.

Input:

A destination node $y\in V$ in a hypergraph $G=(V,E)$, with $n$ nodes $V$, and
$m$ hyperarcs $E=\\{e_{1},\ldots,e_{m}\\}$ indexed by $1\leq i\leq m$. Each
hyperarc has tail nodes $T_{i}\subseteq V\equiv T_{e_{i}}$and head $h_{i}\in
V\equiv h_{e_{i}}$.

Output:

For all $x\in{V}$, $A[x]=\textbf{true}$ if there is a hyperpath-tree
$X\leadsto_{G}y$ such that $x\in{X}$, false otherwise. Time complexity is
$O(t)$ where $t$ is the total size of the input (this is simple depth-first
search on the projected regular graph).

begin

for  _$x\in{V}$_ do $A[x]\leftarrow\textbf{false}$

USE(y)

$\textbf{USE}(y)\equiv$ begin

$A[y]\leftarrow\textbf{true}$

for  _$t\in T_{i}$_ do

if  _$\neg A[t]$_ then

$\textbf{USE}(t)$

Algorithm 3 Single-destination hypergraph reachability

What we are really doing is reversing a hypergraph by interpreting it as a
monadic graph consisting of all edges formed by selecting just one tail of
each hyperarc, and plugging in a default rule for completing the omitted
siblings. We can extend this strategy to the weighted case, using the shortest
hyperpath-tree $X\leadsto v$ ($\pi[v]$) (from from Algorithm 2) for each
omitted sibling $v$. Then we can attribute to each monadic arc the cost of
those omitted hyperpath-trees ($\beta[v]$), in addition to the cost of its
original hyperarc. Then we can perform the usual single-source shortest graph
paths computation[Dijkstra,, 1959] on the this reverse monadic graph.

Since any subtree of a shortest hyperpath-tree $t\in{(X\leadsto y)}$ is a
shortest hyperpath-tree from $X$ to its root-head $h_{label_{t}(())}$, we can
decompose the shortest hyperpath-tree using node $v$ into the shortest
_inside_ $X\leadsto v$ plus the _outside_ $v\leadsto y$ formed by
reconstituting a path in the monadic graph with the default interpretation of
omitted siblings. The outside part is an almost-hyperpath-tree, missing only
an inside subtree for $X\leadsto v$ (an outside tree would be a hyperpath-tree
from $X\cup\\{v\\}\leadsto y$). This is the insight behind the inside-outside
algorithm[Lari and Young,, 1990] for training context free string grammars,
and also its extension to training tree transducers[Graehl and Knight,, 2004].

Note that this decomposition means that the cost functions for hyperarcs must
be separable into an independent sum over parts due to the tails and a part
due to the arc.

In Algorithm 4, we implicitly perform this reversal and monadification of a
hypergraph and obtain for each vertex $v$ the cheapest way to complete the
hyperpath-tree $X\leadsto v$ into $X\leadsto v\leadsto y$ (by that we mean
adjoining some inside hyperpath-tree $X\leadsto v$ with , using parent
$\psi[v]$ with total outside cost (leaving out the cost of $X\leadsto v$)
$\alpha[v]$.

Then, the _utility_ of $v$, or the cost of the cheapest hyperpath-tree using
it, is just $\gamma[v]\equiv\alpha[v]+\beta[v]$ and the utility of hyperarc
$e$ is $\gamma[e]\equiv\alpha[h_{e}]+l_{e}+\sum_{(t,m)\in T_{e}}m\beta[t]$. It
is then easy to select vertices and edges for removal based on some criteria
on their utility relative to the cost of the cheapest hyperpath-tree
$X\leadsto y$, which is $\beta[y]$.

Algorithm 5 selects the minimal subset of the hyperarcs and vertices necessary
to include the best hyperpath-tree $x\leadsto y$ with cost $\beta[y]$ and all
hyperpath-trees with cost no worse than $\beta[y]+\delta$.

Input:

A destination $y\in V$ and default (inside) costs $\beta[v]$ for reaching each
$v\in V$ from $X$ (computed with ViterbiInside), for a hypergraph with $n$
nodes $V$, and $m$ hyperarcs $({e}_{1},\ldots,{e}_{m})$ indexed by $1\leq
i\leq m$.

Each hyperarc has length (i.e. cost to use) $l_{i}\equiv l_{e_{i}}$, a
multiset of tails $T_{i}\equiv T_{e_{i}}\in\mathcal{M}(V)$, and head $h_{i}\in
V\equiv h_{e_{i}}$. The cost for hyperpath-tree from $X\leadsto h_{e}$ using
edge $e$ and the best hyperpath-trees from $X$ to each of its tails $t$ with
cost $\beta[t]$ is $c_{e}=l_{e}+\sum_{(t,m)\in T_{i}}m\beta[t]$ (where m is
the number of occurrences of $t$ in the tails), but other cost functions are
possible - what is important is the ability to build up the cost for using an
edge assuming the default for its tails, and later subtract out the
contribution from the default of a single instance of a tails.

Output:

For all $v\in V$, $\psi[v]$ is the index of the hyperarc used to reach $y$
from $v$ (or 0 if none was taken) with the minimum outside cost
$\alpha[v]$=$\beta[y]-\beta[v]$ given by assuming the default cost way to was
used to reach its siblings from $X$. Time complexity is $O(n\lg{n}+t)$ where
($t$ is the total size of the input) if a Fibonacci heap is used, or
$O(m\lg{n}+t)$ if a binary heap is used.

begin

for  _$x\in V$_ do

$\psi[x]\leftarrow 0$

$\alpha[x]\leftarrow\infty$

$\textit{Adj}^{-1}[x]\leftarrow\\{\\}$

for  _$1\leq i\leq m$ , index of a hyperarc
$(T_{i}=\\{x_{1},\ldots,x_{k}\\})\rightarrow^{l_{i}}\\{h_{i}\\}$_ do

for  _$1\leq j\leq k$_ do
$\textit{Adj}^{-1}[h_{i}]\leftarrow\textit{Adj}^{-1}[h_{i}]\cup\\{x_{j}\\}$

$\alpha[y]\leftarrow 0$

$Q\leftarrow\textbf{HEAP-{CREATE}}()$

$\textbf{HEAP-{INSERT}}(Q,y,0)$

while  _$Q\neq\emptyset$_ do

$x\leftarrow\textbf{HEAP-{EXTRACT-MIN}}(Q)$

for  _$i\in\textit{Adj}^{-1}[x]$_ do

/* edge $i$ with $x$ as a head */

$c\leftarrow\alpha[x]+l_{i}+\sum_{(t,m)\in T_{i}})m\beta[t]$ /* c=total cost
of $X\leadsto e_{i}\leadsto y$ */

for  _$t\in T_{i}$_ do

$c^{\prime}\leftarrow c-\beta[t]$ /* $c^{\prime}$ is the proposed improved
outside cost for $t$ through $e_{i}$, removing $X\leadsto t$ */

if  _$c^{\prime} <\alpha[t]$_ then

if  _$\alpha[h_{i}]=\infty$_ then $\textbf{HEAP-{INSERT}}(Q,t,c^{\prime})$

else $\textbf{HEAP-{DECREASE-KEY}}(Q,t,c^{\prime})$

$\psi[t]\leftarrow i$

$\alpha[t]\leftarrow c^{\prime}$

Algorithm 4 ViterbiOutside \- single-destination, shortest outside hyperpath-
trees

Input:

$\beta[v]$ and $\alpha[v]$, the Viterbi inside and outside costs of each
vertex V over all hyperpath-trees from $X\leadsto y$ (computed with
ViterbiInside and ViterbiOutside) in a hypergraph $G=(V,E)$ with $m$ hyperarcs
$E=\\{e_{1},\ldots,e_{m}\\}$ indexed by $1\leq i\leq m$. Each hyperarc has
tail nodes $T_{i}\subseteq V\equiv T_{e_{i}}$and head $h_{i}\in V\equiv
h_{e_{i}}$. The cost for hyperpath-tree from $X\leadsto h_{e}$ using edge $e$
and the best hyperpath-trees from $X$ to each of its tails $t$ with cost
$\beta[t]$ is $c_{e}=l_{e}+\sum_{t\in T_{i}}m_{t}\beta[t]$, where $l_{e}$ is
the weight on hyperarc $e$ and $m_{t}$ is a weight, e.g. the number of
occurrences of $t$ in the rhs of a grammar production.

$\delta$ is a beam (cost distance from the best hyperpath-tree).

Output:

For all $x\in{V\cup E}$, $\gamma[x]$ is the cost of the best hyperpath-tree
$t\in{(X\leadsto_{G}y)}$ such that $x$ is used in $t$, or $\infty$ if none
exists, $\kappa[x]=\textbf{true}$ iff that cost is not more worse than
$\delta$ from the best $\beta[y]$.

Time complexity is $O(t)$ where $t$ is the total size of the input. (total
complexity including ViterbiInside is $O(n\lg{n}+t)$).

begin

$l\leftarrow\beta[y]+\delta$

for  _$v\in{V}$_ do

$\gamma[v]\leftarrow\beta[v]+\alpha[v]$

for  _$e\in{E}$_ do

$\gamma[e]\leftarrow\alpha[h_{e}]+l_{e}+\sum_{t\in T_{i}}m_{t}\beta[t]$

for  _$x\in{V\cup E}$_ do $\kappa[x]\leftarrow(\gamma[x]\leq l)$

Algorithm 5 Prune relatively-useless vertices and hyperarcs

## References

  * [Dijkstra,, 1959] Dijkstra, E. W.  1959\.  A note on two problems in connection with graphs.  Numerical Mathematics, 1:269–271.
  * [Graehl and Knight,, 2004] Graehl, Jonathan and Kevin Knight.  2004\.  Training tree transducers.  In Proceedings of the 2004 Meeting of the North American chapter of the Association for Computational Linguistics (NAACL-04).
  * [Hopcroft and Ullman,, 1979] Hopcroft, John and Jeffrey Ullman.  1979\.  Introduction to Automata Theory, Languages, and Computation.  Addison-Wesley Series in Computer Science. Addison-Wesley, London.
  * [Knight and Graehl,, 2005] Knight, K. and J. Graehl.  2005\.  An overview of probablistic tree transducers for natural language processing.  In Proceedings of the Sixth International Conference on Intelligent Text Processing and Computational Linguistics (CICLing).
  * [Knuth,, 1977] Knuth, D.  1977\.  A generalization of Dijkstra’s algorithm.  Info. Proc. Letters, 6(1).
  * [Lari and Young,, 1990] Lari, K. and S. J. Young.  1990\.  The estimation of stochastic context-free grammars using the inside-outside algorithm.  Computer Speech and Language, 4, pages 35–56.