Equivalence between AND/OR graphs and context-free grammars
- 1 July 1973
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 16 (7), 444-445
- https://doi.org/10.1145/362280.362302
Abstract
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.Keywords
This publication has 1 reference indexed in Scilit:
- On the Optimal Solutions to AND/OR Series-Parallel GraphsJournal of the ACM, 1971