Multiple initial states are not needed: we can use a single start state Q i , and instead of each initial state q with starting weight w add the rule (Q i , TRUE) → w (q, ()) (where TRUE(t) ≡ 1, ∀t).
we define the binary relation ⇒ X for xR tranducer X on T Σ∪∆∪Q ×(paths×R) * , pairs of partially transformed (working) trees and derivation histories: b is derived from a by application of a rule (q, pat) → w r to an unprocessed input subtree a ↓ i which is in state q, replacing it by output given by r, with its nonterminals replaced by the instruction to transform descendant input subtrees at relative path i ′ in state q ′ .