Hoorcollege 5 Apply modify algebra

Question 1

Graph algebras

Answer 1

Terms contain symbols representing operations
* There is more than one way to build a graph

Question 2

HR Algebra

Answer 2

• Can rename source names ren{rt -> s} (cat, rt) = (cat, s)
  rename s->g (G) is the function
• Can forget source names: fs(cat, s) = (cat)
  forget s (G) is the function
• Merge (||): put g and h together and merge any common source

Question 3

Algebras

Answer 3

Set of objects and a set of operations for putting them together

Question 4

Evaluation of a term

Answer 4

Term can be evaluated bottom up
* replace a node label with its interpretation (object or function)
* Apply the functions to the evaluations of their children
* Notation: [[term]] = object in domain

Question 5

S-graph

Answer 5

graph plus a set S of source names and a mapping from S to the nodes of G

Question 6

Apply-modify (AM) algebra

Answer 6

• Apply operation: Combines a head with a complement
• Modify operation: Combines a modifier with a head

Question 7

Graph types

Answer 7

The type of an s- graph is the set of its non-rt source names
* Apply and Modify with types