Re: Interesting article on ARG work

["Dan'l Miller" <optikos@verizon.net>]

On Monday, April 9, 2018 at 4:17:42 PM UTC-5, Niklas Holsti wrote:
> If there are 2 alternative AST subtrees at each choice point, the total 
> number of possible complete ASTs (which is what the later stages of an 
> ordinary compiler would have to process) is exponential in the number of 
> choice points (that is, "@" instances)

Trivially exponential:  at most 2¹ = 2 alternative AST subtrees as some points, because there is only one choice point:  an @-code-is-present on the compiler's command-line versus an @-code-is-elided on the compiler's command line.  Each @-prefixed line is not isomorphic to yet another differently-named macro in the C preprocessor (or M4, p4, etc preprocessors).  For p choicepoints on the compiler command-line, yes you are trivially correct:  “exponential” 2ᵖ but where p is not only constant, but merely p=1, hence GLR's O(pn) asymptotic rate of growth is O(1n) = O(n) and likewise for the at-most twice-as-big AST.  Not @ instances (as counted by lines of code) but @ degrees of freedom on the compiler command-line.  You are not counting the correct things.