Minimum memoization sets versus MFN memoization: two conjectures refuted, with an unbounded gap

Conjecture 1 of arXiv:2606.26678v1 (p. 10) is FALSE for the Glushkov construction: R0 = ((a | a+) b)*, seven parse-tree nodes, has minimum memoization number 1 – attained by b3, which is not a feedback vertex set – while MFN(Gl(R0)) = a1,a2 is a genuine MINIMUM feedback vertex set (mfvs = 2) whose cheapest memoization subset has size 2; neither a1 nor a2 removes IDA

Conjecture 2 of arXiv:2606.26678v1 (p. 10) is FALSE, and directly rather than through the source's Observation 3: for R0 = ((a | a+) b)* no state of MFN(Gl(R0)) can be deleted without re-introducing IDA, so IAR+ returns MFN(Gl(R0)), of size 2, for EVERY order on the states, against a minimum memoization number of 1

The failure of Conjecture 1 is unbounded, not sporadic: for Rk = ((a | a+ |... | a+) b)* with k copies of a+ (size 3k+4), |MFN(Gl(Rk))| = k+1 and every memoization set inside MFN has size k+1, while the minimum memoization number is 1 – so the MFN-restricted optimum, i.e. what IAR+ can reach, is Omega(|R|) times the true optimum (k = 1,2,3,4 checked)

Erratum in arXiv:2606.26678v1, Example 7 (p. 11 of the arXiv PDF): 'By Algorithm 2, the Glushkov PTA would select a1, giving |MFN| = 1' is wrong for (a|a)*. Algorithm 2 takes the union o u o' at an alternation – the smaller-of-two choice is made only at a concatenation – so it returns a1,a2; and a1 could not be the answer in any case, because the star puts last x first = a1,a2 x a1,a2 into follow, giving a2 a self-loop, so a1 is not a feedback vertex set. |MFN(Gl((a|a)*))| = 2 = the MFVS number

Compute-first-values gate: every Glushkov MFN value the source prints is reproduced from the definitions – Example 2 (p. 9) |MFN(Gl((a+)+))| = 1; Examples 3 and 8 (pp. 10, 11) MFN(Gl(((a a? | a a?) a a?)*)) = a5 with minimum memoization number 1; Example 4 (p. 10) MFN(Gl(((a b? | c d?) e f?)*)) = e with minimum memoization number 0 ('no memoization is required at all'); Example 5 (p. 10) MFN(Gl(((a|b|c|d) e)*)) = e

Negative controls: MFN is not always a minimum memoization set (MFN(Gl(a*)) = a1 but no memoization is needed), Conjecture 1 is not false everywhere ((a|a)* and ((a|a)b)* satisfy it, the latter with minimum memoization number 1), and the IDA predicate is neither constantly true nor constantly false

The smallest counterexample to Conjecture 1 over the alphabet a,b has SEVEN parse-tree nodes: Conjecture 1 holds for the Glushkov construction on all 10,560 regexes of size at most 6 and fails on exactly 8 of the 56,457 of size 7, which are ((a|a+)b)* up to swapping the branches of the alternation, exchanging the two letters, and replacing the outer * by +; each has minimum memoization number 1, |MFN| = 2 and mfvs = 2. The range is not vacuous – 104 of the 10,560 regexes of size <= 6, and 1544 of the 67,017 of size <= 7 (so 1440 at size 7 alone), have 0 < minMemoIn(MFN) < |MFN|, the only situation in which the conjecture could fail. Enumeration counts 3, 9, 45, 243, 1431, 8829, 56457

The census extended to size 11 – all 136,524,153 regexes over a,b – by a C program cross-checked against the Lean census (sizes <= 7) and an independent Python implementation (sizes <= 5): Conjecture 1 fails for Gl(R) on 0, 8, 48, 520, 4200, 34928 regexes of sizes 6..11 and for Th(R) on 0, 0, 8, 56, 672, 6072, of which 0, 0, 0, 24, 224, 3272 have an epsilon-loop in the Thompson NFA. The smallest Thompson counterexamples have EIGHT nodes and are epsilon-loop-free: (a(b+|b+))* and ((a+|a+)b)*, with |MFN(Th)| = 2 against a minimum memoization number of 1

The source's proved theorems confirmed over the same 136,524,153 regexes: ZERO violations of Theorem 5 (|MFN(Th(R))| <= |MFN(Gl(R))|), ZERO cases where the Glushkov MFN fails to be a minimum feedback vertex set (Theorem 4), and 1,248,832 where the Thompson MFN is not one (Theorem 3) – every single one of them with an epsilon-loop, i.e. exactly the exception the source states for Algorithm 1, which is thereby confirmed and shown non-vacuous