Research ledger / Experimental summary (generated) · canonical source: experiments/results/SUMMARY.md

Experimental summary (generated by analyze.py)

All costs are counted elementary steps under the cost model stated in each experiment file; wall-clock seconds are in the JSON files.

CGT-EXP-001 binary tree navigation (LCA ops/query)

shape	n	height	workload	R1 pointer	R2 heap-arith	R3 address-LCP	R4 Euler+sparse	R4 build ops	R2 density n/2^(h+1)
complete	256	8	rand	6.7	4.0	2.0	3.0	4609	0.501
complete	256	8	deep	2.0	4.0	6.4	3.0	4609	0.501
complete	1024	10	rand	8.7	4.0	2.0	3.0	22529	0.5
complete	1024	10	deep	2.0	4.0	8.2	3.0	22529	0.5
complete	4096	12	rand	10.7	4.0	2.0	3.0	106497	0.5
complete	4096	12	deep	2.0	4.0	10.2	3.0	106497	0.5
complete	16384	14	rand	12.6	4.0	2.0	3.0	491521	0.5
complete	16384	14	deep	2.0	4.0	12.2	3.0	491521	0.5
complete	65536	16	rand	14.7	4.0	2.0	3.0	2228225	0.5
complete	65536	16	deep	2.0	4.0	14.1	3.0	2228225	0.5
random_bst	256	15	rand	9.2	4.0	2.4	3.0	4609	0.00391
random_bst	256	15	deep	2.0	4.0	11.4	3.0	4609	0.00391
random_bst	1024	21	rand	12.3	4.0	3.0	3.0	22529	0.000244
random_bst	1024	21	deep	2.0	4.0	15.5	3.0	22529	0.000244
random_bst	4096	26	rand	15.1	4.0	2.7	3.0	106497	3.05e-05
random_bst	4096	26	deep	2.0	4.0	18.5	3.0	106497	3.05e-05
random_bst	16384	31	rand	18.1	4.0	2.5	3.0	491521	3.81e-06
random_bst	16384	31	deep	2.0	4.0	21.8	3.0	491521	3.81e-06
random_bst	65536	37	rand	20.8	4.0	2.6	3.0	2228225	2.38e-07
random_bst	65536	37	deep	2.0	4.0	25.9	3.0	2228225	2.38e-07
path	256	255	rand	86.3	16.0	87.3	3.0	4609	2.21e-75
path	256	255	deep	2.0	16.0	212.5	3.0	4609	2.21e-75
path	1024	1023	rand	334.1	64.0	346.4	3.0	22529	5.7e-306
path	1024	1023	deep	2.0	64.0	853.9	3.0	22529	5.7e-306
path	4096	4095	rand	1379.5	256.0	1371.8	3.0	106497	n·2^-4096 (underflow)
path	4096	4095	deep	2.0	256.0	3403.0	3.0	106497	n·2^-4096 (underflow)
path	16384	16383	rand	5459.6	1024.0	infeasible (Θ(n²) chars)	3.0	491521	n·2^-16384 (underflow)
path	16384	16383	deep	2.0	1024.0	infeasible (Θ(n²) chars)	3.0	491521	n·2^-16384 (underflow)

CGT-EXP-002 reachability: search vs closure vs path grammar

family	n	m	P(reach)	BFS ops/q	TC build ops	break-even Q* (ops)	Q* (wall)	TC bits	zlib bits	n²/4	path-grammar lin firings	nonlin firings	closure pairs
gnp_d0.8	256	204	0.01	5.2	1276	307	356	65536	7104	16384	557	1582	812
gnp_d3	256	768	0.88	305.1	1168	4	10	7680	1704	16384	175015	25807232	57877
dag_d2	256	512	0.03	18.3	2816	163	165	65536	14816	16384	2486	8623	2501
forest	256	254	0.03	7.5	1526	235	288	65536	8496	16384	1056	3835	1312
bipartite_p0.5	256	8240	0.18	49.3	41456	858	509	65536	20256	16384	8240	8240	8496
gnp_d0.8	1024	819	0.01	9.7	14947	1717	757	1048576	43520	262144	4117	–	5133
gnp_d3	1024	3072	0.89	1226.6	6480	5	10	119808	9152	262144	2769847	–	926562
dag_d2	1024	2048	0.01	21.8	35840	1723	652	1048576	97336	262144	11887	–	12460
forest	1024	1014	0.00	5.1	18262	4411	1554	1048576	47136	262144	4161	–	5185
bipartite_p0.5	1024	130965	0.15	198.6	2227429	11272	2139	1048576	281960	262144	130965	–	131989
gnp_d0.8	4096	3276	0.00	9.2	216716	26558	4867	16760832	309608	4194304	–	–	20083
gnp_d3	4096	12288	0.90	4625.5	55104	12	13	2048000	93848	4194304	–	–	14742352
dag_d2	4096	8192	0.01	25.5	536576	21939	2877	16777216	615368	4194304	–	–	52647
forest	4096	4056	0.00	11.3	267736	25969	4327	16777216	304320	4194304	–	–	25154

Forest interval labels (M4): n=256: build 766 ops, 5120 bits, 1 op/q, break-even Q*=118; n=1024: build 3062 ops, 24576 bits, 1 op/q, break-even Q*=740; n=4096: build 12248 ops, 114688 bits, 1 op/q, break-even Q*=1188

Path retrieval given the closure (DAG/forest): dag_d2 n=256: 13.2 ops for mean length 2.4; forest n=256: 8.6 ops for mean length 2.3; dag_d2 n=1024: 17.7 ops for mean length 3.8; dag_d2 n=4096: 8.0 ops for mean length 2.0

CGT-EXP-003 language-constrained reachability

n	avg deg	L	Q	product states	unconstrained states	ratio	vertices misreported by unconstrained search
200	1.5	`a*`	1	1.4	57.0	0.025	55.6
200	1.5	`(ab)*c`	3	2.8	57.0	0.048	56.6
200	1.5	`ScS`	2	60.6	57.0	1.062	0.9
200	1.5	`even_a`	2	110.5	57.0	1.938	1.9
200	1.5	`mod5_len`	5	280.6	57.0	4.919	0.4
2000	1.5	`a*`	1	1.8	704.0	0.003	702.2
2000	1.5	`(ab)*c`	3	3.4	704.0	0.005	703.2
2000	1.5	`ScS`	2	784.9	704.0	1.115	0.9
2000	1.5	`even_a`	2	1406.6	704.0	1.998	0.1
2000	1.5	`mod5_len`	5	3514.4	704.0	4.992	0.8
2000	4.0	`a*`	1	351.6	1868.8	0.188	1517.2
2000	4.0	`(ab)*c`	3	1679.2	1868.8	0.899	1311.9
2000	4.0	`ScS`	2	3399.0	1868.8	1.819	0.1
2000	4.0	`even_a`	2	3737.4	1868.8	2.000	0.0
2000	4.0	`mod5_len`	5	9343.4	1868.8	5.000	0.0
20000	4.0	`a*`	1	4040.2	19619.0	0.206	15578.8
20000	4.0	`(ab)*c`	3	12257.9	19619.0	0.625	15503.1
20000	4.0	`ScS`	2	36011.7	19619.0	1.836	0.1
20000	4.0	`even_a`	2	39238.1	19619.0	2.000	0.0
20000	4.0	`mod5_len`	5	98095.1	19619.0	5.000	0.0

Walk enumeration (tiny graph, n=12) vs product construction:

L	max walk length	walks explored	status	product states
`a*`	4	25	exact	4
`a*`	8	81	exact	4
`a*`	12	169	exact	4
`a*`	12	169	exact	4
`(ab)*c`	4	16	exact	15
`(ab)*c`	8	47	exact	15
`(ab)*c`	12	128	exact	15
`(ab)*c`	36	42184	exact	15
`ScS`	4	181	INCOMPLETE	21
`ScS`	8	11676	exact	21
`ScS`	12	691238	exact	21
`ScS`	24	2000001	aborted(cap)	21
`even_a`	4	181	exact	22
`even_a`	8	11676	exact	22
`even_a`	12	691238	exact	22
`even_a`	24	2000001	aborted(cap)	22
`mod5_len`	4	181	INCOMPLETE	55
`mod5_len`	8	11676	exact	55
`mod5_len`	12	691238	exact	55
`mod5_len`	60	2000001	aborted(cap)	55

CGT-EXP-004 forests and minimal-DAG grammars

family	n	DAG nodes g	DAG edges	size ratio	access ops/q (explicit = 1)	new rules per relabel	live g after k relabels
repetitive_forest	64000	163	372	0.0042	16.3	5.2	[[1, 166], [10, 217], [50, 423], [200, 1176]]
random_forest	64000	16302	39605	0.4402	16.5	5.3	[[1, 16302], [10, 16311], [50, 16366], [200, 16559]]
full_binary_h15	65535	16	30	0.0004	22.0	15.1	[[1, 29], [10, 124], [50, 491], [200, 1521]]
monadic_path	65536	65536	65535	1.0000	32710.4	32089.4	[[1, 65536], [10, 65536], [50, 65536], [200, 65536]]

CGT-EXP-005 dynamic workloads (total counted ops over 4000 operations)

workload	S1 BFS	S2 lazy rebuild	S3 incremental	S4 memo	cheapest
query_only_uniform	62223	21641	21641	66121	S2_rebuild
query_only_repetitive	30216	21641	21641	4077	S4_memo
query_only_adversarial	1000000	21641	21641	228250	S2_rebuild
99q_1ins_uniform	67192	869944	75080	71145	S1_bfs
90q_10ins_uniform	242024	6775863	602748	245653	S1_bfs
90q_10ins_adversarial	1780567	7546028	661186	1770413	S3_incremental
90q_10mixed(50%del)_adversarial	660797	6400929	3573555	658531	S4_memo
50q_50mixed(50%del)_uniform	26624	17535647	12550168	28608	S1_bfs
90q_10mixed(50%del)_repetitive	43685	6623745	3864605	27939	S4_memo

CGT-EXP-006 solution grammars for CNF (residual-dedup automaton)

family	k	median nodes	log2(nodes)/k
3cnf_r4.26	8	49	0.702
3cnf_r4.26	12	154	0.606
3cnf_r4.26	16	1205	0.640
3cnf_r4.26	20	4349	0.604
3cnf_r4.26	24	9793	0.552
3cnf_r4.26	28	43895	0.551
3cnf_r2.0	8	58	0.732
3cnf_r2.0	12	300	0.686
3cnf_r2.0	16	989	0.622
3cnf_r2.0	20	5290	0.618
3cnf_r2.0	24	21102	0.599
3cnf_r2.0	28	52865	0.560
2cnf_r1.0	8	27	0.594
2cnf_r1.0	12	72	0.514
2cnf_r1.0	16	155	0.455
2cnf_r1.0	20	381	0.429
2cnf_r1.0	24	947	0.412
2cnf_r1.0	28	1326	0.370

Model comparison on medians (descriptive; k ≤ 28 is far too small to decide asymptotics):

family	exp fit: log2 N = a + b·k (b, R²)	poly fit: log2 N = a + c·log2 k (c, R²)
3cnf_r4.26	b=0.492, R²=0.987	c=5.45, R²=0.975
3cnf_r2.0	b=0.500, R²=0.994	c=5.53, R²=0.979
2cnf_r1.0	b=0.290, R²=0.988	c=3.22, R²=0.983

CGT-EXP-007 grammar shape: right-linear vs doubling path grammar

family	n	closure pairs	linear firings	= THM-004 formula	linear parallel depth	doubling firings	doubling parallel depth
path	64	2016	2016	yes	63	81500	7
path	128	8128	8128	yes	127	675004	8
path	256	32640	32640	yes	255	5495164	9
path	512	130816	130816	yes	511	44348156	10
gnp_d1.5	64	948	1295	yes	15	12746	5
gnp_d1.5	128	3895	5653	yes	26	172806	6
gnp_d1.5	256	21482	30155	yes	26	3327666	6
gnp_d1.5	512	77844	116121	yes	29	20723742	6
dag_d2	64	453	577	yes	6	1825	4
dag_d2	128	1193	1466	yes	7	5590	4
dag_d2	256	2711	3096	yes	10	13478	5
dag_d2	512	4694	4950	yes	8	16602	4

CGT-EXP-008 compiled move words (THM-006) and arbitrary-shape tables (THM-007)

structure	workload	L	compile ops	compiled ops/application	step-by-step ops/application	defined fraction	break-even applications
heap-shaped tree n=1000000	random_words	8	32	5.0	7.7	0.058	11.7
heap-shaped tree n=1000000	random_words	64	256	5.0	11.6	0.004	38.5
heap-shaped tree n=1000000	random_words	512	2048	5.0	28.9	0.000	85.7
heap-shaped tree n=1000000	random_words	4096	16384	5.0	130.2	0.000	130.9
heap-shaped tree n=1000000	walk_words	8	32	5.0	16.0	1.000	2.9
heap-shaped tree n=1000000	walk_words	64	256	5.0	117.7	0.906	2.3
heap-shaped tree n=1000000	walk_words	512	2048	5.0	933.0	0.907	2.2
heap-shaped tree n=1000000	walk_words	4096	16384	5.0	7419.8	0.905	2.2
random pointer tree n=20000	table by simulation	8	135205 (build)	1 (lookup; 20000 words)	–	0.752	–
random pointer tree n=20000	table by simulation	64	321282 (build)	1 (lookup; 20000 words)	–	0.045	–
random pointer tree n=20000	table by simulation	512	170158 (build)	1 (lookup; 20000 words)	–	0.001	–
debruijn_k2_m20	random words	8	8	1	8.0	–	–
debruijn_k2_m20	random words	512	512	1	512.0	–	–
hypercube_d20	random words	8	8	1	8.0	–	–
hypercube_d20	random words	512	512	1	512.0	–	–
grid_1000x1000	random words	8	8	6	8.0	–	–
grid_1000x1000	random words	512	512	6	485.9	–	–

CGT-EXP-009 PageRank convergence, certification, updates

graph	α	a-priori bound k*	power iterations	true L1 error	certified bound	Gauss–Seidel sweeps
copying_n300 (m=1014)	0.5	36	17	6.78e-12	2.87e-11	24
copying_n300 (m=1014)	0.85	158	28	3.51e-12	5.05e-11	98
copying_n300 (m=1014)	0.9	247	30	3.18e-12	7.16e-11	151
copying_n300 (m=1014)	0.95	521	33	1.51e-12	6.52e-11	307
copying_n300 (m=1014)	0.99	2819	37	2.88e-13	5.74e-11	1561
block_n300 (m=1163)	0.5	36	27	5.75e-11	6.34e-11	16
block_n300 (m=1163)	0.85	158	104	7.57e-11	9.57e-11	56
block_n300 (m=1163)	0.9	247	149	6.30e-11	8.80e-11	85
block_n300 (m=1163)	0.95	521	246	5.09e-11	9.15e-11	170
block_n300 (m=1163)	0.99	2819	485	1.92e-11	9.57e-11	856

insertions	cold iterations	warm-start iterations	L1 shift of the ranking
1	38	27	0.00374
10	38	25	0.0014
100	37	30	0.0189
1000	35	31	0.124
10000	25	25	0.512

ordering	power iterations	Gauss–Seidel sweeps
DAG natural (in-links from later vertices)	43	110
DAG reversed (in-links from earlier vertices)	–	34
block-contiguous	80	64
random-permuted	80	60

CGT-EXP-010 grammar-constrained random surfers (PROP-010)

n	language	\|Q\|	product states	≤ \|Q\|n	iterations	edge-op ratio vs PageRank	top-10 overlap	L1 distance
500	`universal Σ*`	1	500	500	37	1.03	10	0.000
500	`no c: (a	b)*`	1	500	500	119	2.14	5
500	`alternate: (a b)* (a	ε)`	2	786	1000	32	0.46	5
500	`c only after a: (b	a c?)*`	2	786	1000	40	1.37	7
500	`length < 3: (a	b	c)? (a	b	c)? (a	b	c)?`	4
5000	`universal Σ*`	1	5000	5000	38	1.03	10	0.000
5000	`no c: (a	b)*`	1	5000	5000	42	0.76	9
5000	`alternate: (a b)* (a	ε)`	2	8006	10000	46	0.66	6
5000	`c only after a: (b	a c?)*`	2	8006	10000	38	1.30	9
5000	`length < 3: (a	b	c)? (a	b	c)? (a	b	c)?`	4