A generalization of AND/OR graphs is introduced as a problem solving model, in which subproblem interdependence in problem reduction can be explicitly accounted for. An ordered-search algorithm is given to find a solution. The algorithm is proven to be admissible and optimal. Examples are given which show the application of the formalism to problems which cannot be modelled by AND/OR graphs. Generalized AND/OR graphs are finally shown to be equivalent to type O grammars. Finding a solution of a generalized AND/OR graph is shown to be equivalent lo deriving a sentence in the corresponding type 0 grammar.

Generalized AND/OR graphs and their relation to formal grammars.

SIROVICH, Franco
1973-01-01

Abstract

A generalization of AND/OR graphs is introduced as a problem solving model, in which subproblem interdependence in problem reduction can be explicitly accounted for. An ordered-search algorithm is given to find a solution. The algorithm is proven to be admissible and optimal. Examples are given which show the application of the formalism to problems which cannot be modelled by AND/OR graphs. Generalized AND/OR graphs are finally shown to be equivalent to type O grammars. Finding a solution of a generalized AND/OR graph is shown to be equivalent lo deriving a sentence in the corresponding type 0 grammar.
1973
http://www.di.unito.it/~franco/PUBS/TR/N4.pdf
Artificial Intelligence; Search Algorithms; Problem Solving.
G. Levi; Franco Sirovich
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/45363
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact