PROBABILISTIC GRAPH GRAMMARS

Article type: Research Article

Authors: Mosbah, Mohamed

Affiliations: LaBRI, Université de Bordeaux-I, 351, Cours de la Libération, 33405 Talence, France

Note: [] Electronic mail: [email protected]

Abstract: In a probabilistic graph grammar, each production has a probability attached to it. This induces a probability assigned to each derivation tree, and to each derived graph. Conditions for this probability function to be a probabilistic measure are discussed. The statistical properties of the generated language are investigated. We show how to compute the average size of an inductive function, and the probability of an inductive graph predicate. A relationship can be established between production probabilities and some statistical information of the generated language. This way, probabilities can be assigned to productions so that the generated graphs satisfy some statistical condition.

DOI: 10.3233/FI-1996-263406

Journal: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 341-362, 1996