摘要: We introduce probabilistic graph grammars. These are grammars with additional probabilities attached to the production rules. This adds a use ordinary describe some methods from numerical analysis compute statistical measures of generated graphs. show how determine average size an inductive function, or probability property.
springer.com
sci-hub.st 参考文章(13)
Clemens Lautemann, Efficient Algorithms on Context-Free Graph Grammars international colloquium on automata languages and programming. pp. 362- 378 ,(1988)
A. Habel, Hyperedge Replacement: Grammars and Languages ,(1992)
Hartmut Ehrig, Grzegorz Rozenberg, M. Nagl, Azriel Rosenfeld, Graph Grammars and Their Application to Computer Science: 3rd International Workshop Warrenton, Virginia, Usa, December 2-6, 1986 ,(1988)
B. Courcelle, An axiomatic definition of context-free rewriting and its application to NLC graph grammars Theoretical Computer Science. ,vol. 55, pp. 141- 181 ,(1987) , 10.1016/0304-3975(87)90102-2
Sandra E. Hutchins, Moments of string and derivation lengths of stochastic context-free grammars Information Sciences. ,vol. 4, pp. 179- 191 ,(1972) , 10.1016/0020-0255(72)90011-4
B. Courcelle, M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs Theoretical Computer Science. ,vol. 109, pp. 49- 82 ,(1993) , 10.1016/0304-3975(93)90064-Z
Michel Bauderon, Bruno Courcelle, Graph expressions and graph rewritings Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 20, pp. 83- 127 ,(1987) , 10.1007/BF01692060
Stephen Soule, Entropies of probabilistic grammars Information & Computation. ,vol. 25, pp. 57- 74 ,(1974) , 10.1016/S0019-9958(74)90799-2
Clemens Lautemann, The complexity of graph languages generated by hyperedge replacement Acta Informatica. ,vol. 27, pp. 399- 421 ,(1990) , 10.1007/BF00289017
T.L. Booth, R.A. Thompson, Applying Probability Measures to Abstract Languages IEEE Transactions on Computers. ,vol. C-22, pp. 442- 450 ,(1973) , 10.1109/T-C.1973.223746