Week 5 [2023-05-02 Tue]

We saw that we could represent and construct derivations in different ways.

Our usual bottom-up approach to derivations (represented as trees) could be done instead in terms of dependency graphs.

Furthermore, our inference rules could be read backwards, allowing us to construct derivations top down. This leads to much more non-determinism in the system.

We saw in addition that workspaces, though they seem formally unnecessary for bottom up approaches, are vital for the top-down approach. This is because, top-down, we are splitting a single object into multiple objects, each of which need to be completed before the entire derivation is licensed.