Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Estimate if/when grammars lead to infinite recursion. #7

Open
linas opened this issue Apr 17, 2020 · 0 comments
Open

Estimate if/when grammars lead to infinite recursion. #7

linas opened this issue Apr 17, 2020 · 0 comments

Comments

@linas
Copy link
Member

linas commented Apr 17, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant