Candidate and search space for given input sequence
Given a particular input sequence w, the candidate trees for this sequence are
  • all the trees that can be generated by the tree grammar
  • which spell out w as their sequence of leaves (in left to right order)
So, the search space for input w is the set of all such trees, or if you choose to think of scores, the set of scores that are derived from evaluating these trees in some algebra.
How to find these trees/scores for given w is not your problem. There is a standard device (called a tabulating tree parser) that can compute the trees as well as the scores.
This device also applies the choice function specified with the algebra at intermediate steps.
This means in ADP, after specifying algebra(s) and grammar, you have no other code to add to obtain a running program.
background image
university bielefeld AG PI BiBiServ
ambient picture