Analysis of Extremal Problems on Grammars, Hypergraphs, and And-Or Graphs based on Generalized Bellman Equations

G. Adelson-Velsky, E. Levner (Israel), and A. Gelbukh (Mexico)

Keywords

Extremal paths, grammars, hypergraphs, AND-OR graphs

Abstract

We introduce generalized Bellman equations (GBE) which in a uniform way yield min-valued terminal strings in grammars, and extremal paths in hypergraphs and AND-OR graphs. We show that in general case the opti mal solutions of three extremal problems are different though in some non-trivial cases they turn out to be iden tical. This uniform approach permits obtaining new classes of polynomial-solvable extremal problems on grammars, hypergraphs, and AND-OR graphs. Specifi cally, we introduce superior AND-OR graphs and suggest a polynomial algorithm for finding the extremal paths.

Important Links:

• DOI:
• From Proceeding (431) Advances in Computer Science and Technology - 2004

Go Back