Research and Advances

Equivalence between AND/OR graphs and context-free grammars

Recent research in artificial intelligence has led to AND/OR graphs as a model of problem decomposition (Nilsson [3]; Simon and Lee [4]). However, AND/OR graphs of a restricted type are equivalent to context-free grammars. This can be set-up formally (the beginnings of a formalism of AND/OR graphs is contained in [4]), but the formalism is so obvious that a brief discussion and example suffice.

Advertisement

Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved