diff 295faa5..a62ba7d two_way_nondeterministic_complement_v2.txt
diff --git a/two_way_nondeterministic_complement_v2.txt b/two_way_nondeterministic_complement_v2.txt
index 91a726e..3b99dec 100644
--- a/two_way_nondeterministic_complement_v2.txt
+++ b/two_way_nondeterministic_complement_v2.txt
@@ -97,10 +97,14 @@ state and scanned symbol.
--------------------------------------------------------------------------------
A binary relation on a set X is a set of ordered pairs, i.e. a subset of
-X x X. We write "a R b" as shorthand for "(a,b) is in R".
+X x X. We write "a R b" as shorthand for "(a,b) is in R". For example,
+on X = {1,2,3}, the relation R = {(1,2),(2,3)} says 1 R 2 and 2 R 3.
Relations compose in PATH ORDER: a (R S) b holds iff there is some c with
-a R c and c S b. So we apply R first and then S.
+a R c and c S b. So we apply R first and then S. In the example above,
+R R = {(1,3)}: from 1 we reach 2 via R, then 3 via R; no other pairs
+survive. The EMPTY relation (the empty set of pairs) has no pairs at all,
+and the IDENTITY relation I_X = {(p,p) : p in X} leaves every p fixed.
Fix the set H of h = n-2 points. Let
@@ -150,9 +154,6 @@ the machine accepts w iff r(w) is nonempty. For the empty word the guessed
p_0 sits immediately on the right endmarker and stays into q_acc, so the
empty word is also accepted, matching r(epsilon) = I_H nonempty. QED
-The task is now to show that the COMPLEMENT (Sigma^* minus L_H) needs
-exponentially many states, even for a nondeterministic two-way machine.
-
--------------------------------------------------------------------------------
3. PATH DIAGRAMS
--------------------------------------------------------------------------------
@@ -558,13 +559,27 @@ P_e (K_e F_e) = K_e F_e let us move from p to any q in C, using q P_e p and
p P_e q, without changing the set; the two factors of the rectangle are
unchanged.
-Coverage: from F_e K_e F_e = F_e we get F_e P_e^k F_e = F_e for every k >= 1.
-Given a pair (u,v) in F_e, choose a witness of this for a power k with k > m.
-Along the P_e part, some of the m+1-or-more labels repeats; call the repeated
-label p. The portion of the P_e-path between two occurrences of p is a loop
-p P_e p, so p is recurrent. The part before p lies in F_e P_e^j <= F_e K_e
-and the part after p in P_e^j F_e <= K_e F_e (for j >= 0, using reflexivity of
-K_e when j = 0). So (u,v) lies in the rectangle of the recurrent class of p.
+Coverage: we factor an arbitrary pair (u,v) in F_e through a recurrent point.
+Because P_e = K_e F_e K_e and F_e K_e F_e = F_e,
+
+ F_e P_e = F_e K_e F_e K_e = F_e K_e ,
+ P_e F_e = K_e F_e K_e F_e = K_e F_e ,
+
+so, since K_e is reflexive, induction on j >= 0 gives
+
+ F_e P_e^j <= F_e K_e and P_e^j F_e <= K_e F_e .
+
+Also P_e is idempotent, so F_e P_e^k F_e = F_e P_e F_e = F_e K_e F_e = F_e
+for every k >= 1. Fix k > m and expand (u,v) in F_e = F_e P_e^k F_e as
+
+ u F_e c_1 P_e c_2 P_e ... P_e c_k P_e c_{k+1} F_e v .
+
+The k+1 labels c_1, ..., c_{k+1} all lie in the m-element set D+, so two of
+them coincide: c_i = c_j with i < j. Idempotence of P_e then gives
+c_i P_e^{j-i} c_j = c_i P_e c_i, so p = c_i is recurrent. The prefix ending
+at p lies in F_e P_e^{i-1} <= F_e K_e, giving u F_e K_e p; the suffix starting
+at p lies in P_e^{k+1-i} F_e <= K_e F_e, giving p K_e F_e v. Thus (u,v) lies
+in the rectangle of the recurrent class of p, so the rectangles cover F_e.
Now suppose C is not missing from z. Then for p in C the loop
p K_e F_z K_e p holds. Inserting it between the two halves of the rectangle,
@@ -599,13 +614,14 @@ that, for every z in the corner e T_m e with M_e(z) <= J and u z v in d T_m d
PROOF. We fix witnesses once and for all, independent of z.
Fix a positive class C of C_d with representative x. Its recurrence reads
-x K_d^+ F_d K_d^+ x, and after substituting d = u e v the middle F_d = F_{uev}
-is a concrete finite path through the three diagrams u, e, v. That path uses
-finishing moves out of cells; whenever it crosses the MIDDLE diagram e it uses
-a through edge of e (a pair of F_e, or of B_e, according to sign). For each
-such middle through edge pick, using Lemma 7.2, an e-recurrent class whose
-rectangle covers it. Do the same for every negative class, using
-x K_d^- B_d K_d^- x. These choices depend only on u, e, v, d, not on z.
+x K_d^+ F_d K_d^+ x. Substituting d = u e v, the edge F_d = F_{uev} expands
+into a finite path that enters u, crosses e, and exits through v (with
+possible return loops at each boundary). Every time this path crosses the
+middle factor e it uses a through edge of e (a pair of F_e, or of B_e for
+the negative sign). For each such middle edge pick, using Lemma 7.2, an
+e-recurrent class whose rectangle covers it. Do the same for every negative
+class, using x K_d^- B_d K_d^- x. These choices depend only on u, e, v, d,
+not on z.
Now define J'. A class C of C_d is MARKED when any e-class chosen along its
fixed witness lies in J. Let J' be the set of marked classes.
@@ -1113,9 +1129,10 @@ which rearranges to
s >= (1/2) * 2^floor((n-4)/127) - 1 .
-The right-hand side grows exponentially with n and is bounded by no polynomial.
-Hence no single polynomial, independent of the alphabet, bounds the number of
-states needed to complement an n-state 2NFA. QED
+The right-hand side grows exponentially with n and is bounded by no polynomial
+(for any fixed degree d, the ratio 2^floor((n-4)/127) / n^d tends to infinity
+as n grows). Hence no single polynomial, independent of the alphabet, bounds
+the number of states needed to complement an n-state 2NFA. QED
A word of honesty about the alphabet. The alphabet Sigma_n = R_H has
|Sigma_n| = 2^{(n-2)^2} letters and grows with n. The theorem is about bounds