#3 Validation: detect runaway expansion

Closed
opened 3 years ago by fnordomat · 1 comments

validate_grammar should probably reject grammars that tend to expand too quickly.

Idea from dynamical systems theory: define a quantitative transition matrix $A_{i,j}$ = expected number of occurrences of nonterminal $j$ in right hand sides of rules for nonterminal $i$ (weighted with rule weights). This is a nonnegative square matrix and we can approximate its "Perron-Frobenius" eigenvalue. If $\lambda_max \ge 1$, this should be a sure sign that the grammar tends to have runaway derivations. If it is $<1$ on the other hand, then expansion tends to die down.

validate_grammar should probably reject grammars that tend to expand too quickly. Idea from dynamical systems theory: define a quantitative transition matrix $A_{i,j}$ = expected number of occurrences of nonterminal $j$ in right hand sides of rules for nonterminal $i$ (weighted with rule weights). This is a nonnegative square matrix and we can approximate its "Perron-Frobenius" eigenvalue. If $\lambda_max \ge 1$, this should be a sure sign that the grammar tends to have runaway derivations. If it is $<1$ on the other hand, then expansion tends to die down.
fnordomat commented 3 years ago
Owner

check implemented

check implemented
Sign in to join this conversation.
No Label
No Milestone
No assignee
1 Participants
Loading...
Cancel
Save
There is no content yet.