opencog/generate

Estimate if/when grammars lead to infinite recursion.

linas opened this issue · 0 comments

linas commented

For simple grammars (and maybe for all grammars?) its seems possible to determine in advance, if they will lead to infinite recursion, on average. Infiinte recusion happens if, on average the likelihood of picking an arity-three (or larger) section exceeds the likelihood of picking an arity-one section. That is, an arity-n section increases the number of open connectors by (n-2) on average, while an arity-one link reduces the number of open connectors by one. Since each section is weighted with the probability of it being chosen, it is a "simple matter" of computing the expectation values.

Its not entirely simple, when there are multiple connector types, but ... it seems feasible to do in code, and can provide advance warning of infinite recursion, before generation is even started. Seems low-priority, for now. See the export-to-gml.scm example for an explicit calculation for the simple case.