Graph-grammar decoding

[ihh]

Find an "ideal" generator by beginning with a beam search, then iteratively & greedily applying the best expansion of a given graph grammar on the current generator, keeping the generator probabilistically normalized & doing one round of EM to optimize the probabilities for each possible graphgram rule application.

[ihh]

Information size of a weighted graph with N nodes and T transitions, with weights specified to a fixed width of W/lg(10) decimal places, is T(2lg(N) + W)
Use something like this as a prior on generators, i.e. a size penalty. Each new generator must score at least this much (on the given acceptor) to be worth exploring. Decoder specifies W, and can set W=0 for non-weighted decoding.