Theory Wrap_Prefix_Runs

theory Wrap_Prefix_Runs
  imports Wrap_Prefix_Patch
begin

section ‹Runs of the patched wrap›

text ‹The patched wrap's first steps are its encoder's, forced because the
  encoder is deterministic; the runs below are the canonical ones, and
  ‹relpow_forced_split› below says every other run of the wrap or of
  its patch agrees with them.  None of the arguments assumes the
  simulated machine deterministic.›

subsection ‹Forced splitting›

lemma relpow_backward:
  assumes backward: "⋀x y. (x, y) ∈ R ⟹ G y ⟹ G x"
      and run: "(a, b) ∈ R ^^ n" and good: "G b"
  shows "G a"
  using run good
proof (induction n arbitrary: b)
  case 0
  then show ?case by simp
next
  case (Suc n)
  obtain b' where "(a, b') ∈ R ^^ n" and "(b', b) ∈ R"
    using Suc.prems(1) by (rule relpow_Suc_E)
  then show ?case using Suc.IH backward Suc.prems(2) by blast
qed

text ‹Against a run that is good at step ‹p›, a run of length ‹n› from
  the same configuration either passes through that point, or stops
  short of it while still good.›

lemma relpow_forced_split:
  assumes unique: "⋀x y z. (x, y) ∈ R ⟹ (x, z) ∈ R ⟹ G x ⟹ y = z"
      and backward: "⋀x y. (x, y) ∈ R ⟹ G y ⟹ G x"
      and one: "(a, b) ∈ R ^^ p" and good: "G b"
      and two: "(a, c) ∈ R ^^ n"
  shows "p ≤ n ∧ (b, c) ∈ R ^^ (n - p) ∨ n < p ∧ G c"
proof (cases "p ≤ n")
  case True
  have "(a, c) ∈ R ^^ (p + (n - p))" using two True by simp
  then obtain x where ax: "(a, x) ∈ R ^^ p" and xc: "(x, c) ∈ R ^^ (n - p)"
    unfolding relpow_add by blast
  have "b = x" by (rule relpow_forced[where R=R and G=G, OF unique backward one ax good])
  then show ?thesis using True xc by simp
next
  case False
  have "(a, b) ∈ R ^^ (n + (p - n))" using one False by simp
  then obtain y where ay: "(a, y) ∈ R ^^ n" and yb: "(y, b) ∈ R ^^ (p - n)"
    unfolding relpow_add by blast
  have gy: "G y" by (rule relpow_backward[where R=R and G=G, OF backward yb good])
  have "y = c" by (rule relpow_forced[where R=R and G=G, OF unique backward ay two gy])
  then show ?thesis using False gy by simp
qed

lemma wrap_forced_split:
  fixes A :: "('q, 'b) ktm"
  assumes one: "(a, b) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ p"
      and good: "∀q. ktc_state b ≠ W_Run q"
      and two: "(a, c) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ n"
  shows "p ≤ n ∧ (b, c) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (n - p)
    ∨ n < p ∧ (∀q. ktc_state c ≠ W_Run q)"
proof -
  have d: "delta_ktm (encoding_wrap A pack m S) = wrap_delta A pack m S" by simp
  show ?thesis unfolding d
    by (rule relpow_forced_split[where R = "ktm_step (wrap_delta A pack m S)"
        and G = "λC. ∀q. ktc_state C ≠ W_Run q",
        OF wrap_step_unique_non_run wrap_step_back_non_run
        one[unfolded d] good two[unfolded d]])
qed

lemma wrap_prefix_forced_split:
  fixes A :: "('q, 'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool"
  assumes one: "(a, b) ∈ (ktm_step (delta_ktm
        (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ p"
      and good: "∀q. snd (ktc_state b) ≠ W_Run q"
      and two: "(a, c) ∈ (ktm_step (delta_ktm
        (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ n"
  shows "p ≤ n ∧ (b, c) ∈ (ktm_step (delta_ktm
        (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (n - p)
    ∨ n < p ∧ (∀q. snd (ktc_state c) ≠ W_Run q)"
  by (rule relpow_forced_split[where R = "ktm_step (delta_ktm
        (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
      and G = "λC. ∀q. snd (ktc_state C) ≠ W_Run q",
      OF wrap_prefix_step_unique wrap_prefix_step_back_non_run one good two])


subsection ‹The flagged first compression block›

lemma wrap_prefix_first_block:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool" and N :: nat
    and W :: "(('q,'a,'b) wrap_state,('a,'b) wrap_alphabet) ktm"
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and word: "set w ⊆ S" and j: "j < m" "j ≤ length w"
  defines "W ≡ encoding_wrap A pack m S"
      and "P ≡ wrap_prefix_patch W table N"
      and "C ≡ λj. mid_buf_extending_config_gen (k_ktm A) A pack m w 0 j"
  shows "(init_config_ktm P (map Raw w),wrap_flag_config True (C j))
      ∈ (ktm_step (delta_ktm P)) ^^ Suc j"
    and "(init_config_ktm W (map Raw w),C j)
      ∈ (ktm_step (delta_ktm W)) ^^ Suc j"
proof -
  have zero: "C 0 = mid_encoder_config_gen (k_ktm A) A pack m w 0"
    by (simp add: C_def mid_buf_extending_config_gen_def mid_encoder_config_gen_def fun_eq_iff split: nat.split)
  have old_init: "(init_config_ktm W (map Raw w),C 0)
    ∈ ktm_step (delta_ktm W)"
    using init_to_mid_zero[OF valid positive, where pack=pack and w=w and Σu=S]
    by (simp add: W_def zero)
  have new_init: "(init_config_ktm P (map Raw w),wrap_flag_config True (C 0))
    ∈ ktm_step (delta_ktm P)"
  proof -
    have target: "wrap_prefix_target W table N True
        (ktc_state (init_config_ktm W (map Raw w)))
        (λk. ktc_tape (init_config_ktm W (map Raw w)) k
          (ktc_pos (init_config_ktm W (map Raw w)) k)) (ktc_state (C 0))
        = (True,ktc_state (C 0))"
      by (auto simp: W_def C_def
        mid_buf_extending_config_gen_def wrap_prefix_target_def wrap_first_flag_def)
    show ?thesis using wrap_prefix_step[OF old_init target]
      by (simp add: P_def)
  qed
  have prefixes:
    "(init_config_ktm P (map Raw w),wrap_flag_config True (C i))
        ∈ (ktm_step (delta_ktm P)) ^^ Suc i ∧
      (init_config_ktm W (map Raw w),C i)
        ∈ (ktm_step (delta_ktm W)) ^^ Suc i"
    if "i < m" "i ≤ length w" for i
    using that
  proof (induction i)
    case 0
    show ?case using old_init new_init by simp
  next
    case (Suc i)
    have i: "i < m" "i < length w" using Suc.prems by auto
    have old_step: "(C i,C (Suc i)) ∈ ktm_step (delta_ktm W)"
      using mid_buf_extend_step[where i=0 and j=i, OF valid positive word Suc.prems(1)]
        i by (simp add: C_def W_def)
    have k: "0 < k_ktm A" by (rule valid_ktm_k_pos[OF valid])
    have nonempty: "w ≠ []" using i(2) by (cases w) auto
    have target: "wrap_prefix_target W table N True (ktc_state (C i))
      (λk. ktc_tape (C i) k (ktc_pos (C i) k)) (ktc_state (C (Suc i)))
        = (True,ktc_state (C (Suc i)))"
      using i Suc.prems k nonempty
      by (simp add: W_def C_def
        mid_buf_extending_config_gen_def wrap_prefix_target_def wrap_first_flag_def)
    have new_step: "(wrap_flag_config True (C i),wrap_flag_config True (C (Suc i)))
      ∈ ktm_step (delta_ktm P)"
      using wrap_prefix_step[OF old_step target] by (simp add: P_def)
    have ih: "(init_config_ktm P (map Raw w),wrap_flag_config True (C i))
        ∈ (ktm_step (delta_ktm P)) ^^ Suc i"
      "(init_config_ktm W (map Raw w),C i)
        ∈ (ktm_step (delta_ktm W)) ^^ Suc i"
      using Suc.IH[OF i(1)] Suc.prems by auto
    show ?case using relpow_Suc_I[OF ih(1) new_step]
      relpow_Suc_I[OF ih(2) old_step] by blast
  qed
  show "(init_config_ktm P (map Raw w),wrap_flag_config True (C j))
      ∈ (ktm_step (delta_ktm P)) ^^ Suc j"
    and "(init_config_ktm W (map Raw w),C j)
      ∈ (ktm_step (delta_ktm W)) ^^ Suc j"
    using prefixes[OF j] by auto
qed

lemma wrap_prefix_short_run:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool" and N :: nat
    and W :: "(('q,'a,'b) wrap_state,('a,'b) wrap_alphabet) ktm"
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
      and k2: "2 ≤ k_ktm A"
      and pack: "⋀i. i*m < length w ⟹
        pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
  defines "W ≡ encoding_wrap A pack m S"
      and "P ≡ wrap_prefix_patch W table N"
  assumes short: "length w < m" "length w ≤ N"
  shows "(init_config_ktm P (map Raw w),
      wrap_flag_config True (mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w)))
      ∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)"
    and "(wrap_flag_config True (mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w)),
      KConfig (False,if table w then t_ktm W else r_ktm W)
        (ktc_tape (post_encoder_config_gen (k_ktm A) A pack m w))
        (ktc_pos (post_encoder_config_gen (k_ktm A) A pack m w)))
      ∈ ktm_step (delta_ktm P)"
proof -
  let ?C = "mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w)"
  let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
  let ?q = "if table w then t_ktm W else r_ktm W"
  have first: "(init_config_ktm P (map Raw w),wrap_flag_config True ?C)
      ∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)"
    using wrap_prefix_first_block(1)[where A=A and pack=pack and table=table and N=N
      and m=m and w=w and S=S and j="length w"]
      valid positive word short
    by (simp add: W_def P_def)
  have old_first: "(init_config_ktm W (map Raw w),?C)
      ∈ (ktm_step (delta_ktm W)) ^^ Suc (length w)"
    using wrap_prefix_first_block(2)[where A=A and pack=pack
      and m=m and w=w and S=S and j="length w"]
      valid positive word short
    by (simp add: W_def)
  have old_whole: "(init_config_ktm W (map Raw w),?D)
    ∈ (ktm_step (delta_ktm W)) ^^ (length w+2)"
    using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w and Σu=S, OF valid positive word blle k2 pack]
    by (simp add: W_def)
  have goodC: "∀q. ktc_state ?C ≠ W_Run q"
    by (simp add: mid_buf_extending_config_gen_def)
  have last: "(?C,?D) ∈ ktm_step (delta_ktm W)"
    using wrap_forced_split[OF old_first[unfolded W_def] goodC old_whole[unfolded W_def]]
    by (simp add: W_def)
  have k: "0 < k_ktm A" by (rule valid_ktm_k_pos[OF valid])
  have target: "wrap_prefix_target W table N True (ktc_state ?C)
    (λj. ktc_tape ?C j (ktc_pos ?C j)) (ktc_state ?D) = (False,?q)"
    using short k
    by (simp add: W_def wrap_prefix_target_def
      mid_buf_extending_config_gen_def post_encoder_config_gen_def)
  let ?final = "KConfig (False,?q) (ktc_tape ?D) (ktc_pos ?D)"
  have new_last: "(wrap_flag_config True ?C,?final) ∈ ktm_step (delta_ktm P)"
    using wrap_prefix_redirect_step[OF last target] by (simp add: P_def)
  show "(init_config_ktm P (map Raw w),wrap_flag_config True ?C)
      ∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)" by (rule first)
  show "(wrap_flag_config True ?C,?final) ∈ ktm_step (delta_ktm P)" by (rule new_last)
qed

lemma wrap_prefix_long_prefix:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool" and N :: nat
    and W :: "(('q,'a,'b) wrap_state,('a,'b) wrap_alphabet) ktm"
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
      and k2: "2 ≤ k_ktm A"
      and pack: "⋀i. i*m < length w ⟹
        pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
  defines "W ≡ encoding_wrap A pack m S"
      and "P ≡ wrap_prefix_patch W table N"
  assumes long: "N < length w"
  shows "(init_config_ktm P (map Raw w),
      wrap_flag_config False (post_encoder_config_gen (k_ktm A) A pack m w))
      ∈ (ktm_step (delta_ktm P)) ^^ (length w+2)"
proof -
  let ?C = "λj. mid_buf_extending_config_gen (k_ktm A) A pack m w 0 j"
  let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
  have old_whole: "(init_config_ktm W (map Raw w),?D)
    ∈ (ktm_step (delta_ktm W)) ^^ (length w+2)"
    using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w
      and Σu=S, OF valid positive word blle k2 pack]
    by (simp add: W_def)
  have k: "0 < k_ktm A" by (rule valid_ktm_k_pos[OF valid])
  show ?thesis
  proof (cases "length w < m")
    case True
    have first: "(init_config_ktm P (map Raw w),wrap_flag_config True (?C (length w)))
      ∈ (ktm_step (delta_ktm P)) ^^ Suc (length w)"
      using wrap_prefix_first_block(1)[where A=A and pack=pack and table=table and N=N
        and m=m and w=w and S=S and j="length w"] valid positive word True
      by (simp add: W_def P_def)
    have old_first: "(init_config_ktm W (map Raw w),?C (length w))
      ∈ (ktm_step (delta_ktm W)) ^^ Suc (length w)"
      using wrap_prefix_first_block(2)[where A=A and pack=pack
        and m=m and w=w and S=S and j="length w"] valid positive word True
      by (simp add: W_def)
    have goodC: "∀q. ktc_state (?C (length w)) ≠ W_Run q"
      by (simp add: mid_buf_extending_config_gen_def)
    have last: "(?C (length w),?D) ∈ ktm_step (delta_ktm W)"
      using wrap_forced_split[OF old_first[unfolded W_def] goodC old_whole[unfolded W_def]]
      by (simp add: W_def)
    have target: "wrap_prefix_target W table N True (ktc_state (?C (length w)))
      (λj. ktc_tape (?C (length w)) j (ktc_pos (?C (length w)) j))
      (ktc_state ?D) = (False,ktc_state ?D)"
      using long k
      by (simp add: W_def wrap_prefix_target_def wrap_first_flag_def
        mid_buf_extending_config_gen_def post_encoder_config_gen_def)
    have new_last: "(wrap_flag_config True (?C (length w)),wrap_flag_config False ?D)
      ∈ ktm_step (delta_ktm P)"
      using wrap_prefix_step[OF last target] by (simp add: P_def)
    show ?thesis using relpow_Suc_I[OF first new_last] by simp
  next
    case False
    have m_le: "m ≤ length w" using False by simp
    have index: "m-1 < m" "m-1 ≤ length w" using positive m_le by arith+
    let ?B = "mid_encoder_config_gen (k_ktm A) A pack m w 1"
    have first: "(init_config_ktm P (map Raw w),wrap_flag_config True (?C (m-1)))
      ∈ (ktm_step (delta_ktm P)) ^^ m"
      using wrap_prefix_first_block(1)[where A=A and pack=pack and table=table and N=N
        and m=m and w=w and S=S and j="m-1"] valid positive word index
      by (simp add: W_def P_def)
    have old_first: "(init_config_ktm W (map Raw w),?C (m-1))
      ∈ (ktm_step (delta_ktm W)) ^^ m"
      using wrap_prefix_first_block(2)[where A=A and pack=pack
        and m=m and w=w and S=S and j="m-1"] valid positive word index
      by (simp add: W_def)
    have nonempty: "w ≠ []" using positive m_le by (cases w) auto
    have block: "pack (take m w) ∈ Sigma_ktm A"
      using pack[of 0] nonempty by simp
    have close: "(?C (m-1),?B) ∈ ktm_step (delta_ktm W)"
      using mid_buf_close_step[where M=A and pack=pack and c=m and w=w
        and Σu=S and i=0, OF valid positive word _ _ blle k2] m_le block
      by (simp add: W_def)
    have target: "wrap_prefix_target W table N True (ktc_state (?C (m-1)))
      (λj. ktc_tape (?C (m-1)) j (ktc_pos (?C (m-1)) j))
      (ktc_state ?B) = (False,ktc_state ?B)"
      using positive m_le k
      by (simp add: W_def wrap_prefix_target_def wrap_first_flag_def
        mid_buf_extending_config_gen_def mid_encoder_config_gen_def)
    have new_close: "(wrap_flag_config True (?C (m-1)),wrap_flag_config False ?B)
      ∈ ktm_step (delta_ktm P)"
      using wrap_prefix_step[OF close target] by (simp add: P_def)
    have new_block: "(init_config_ktm P (map Raw w),wrap_flag_config False ?B)
      ∈ (ktm_step (delta_ktm P)) ^^ Suc m"
      by (rule relpow_Suc_I[OF first new_close])
    have old_block: "(init_config_ktm W (map Raw w),?B)
      ∈ (ktm_step (delta_ktm W)) ^^ Suc m"
      by (rule relpow_Suc_I[OF old_first close])
    have order: "Suc m ≤ length w+2" using m_le by arith
    have goodB: "∀q. ktc_state ?B ≠ W_Run q"
      by (simp add: mid_encoder_config_gen_def)
    have suffix: "(?B,?D) ∈ (ktm_step (delta_ktm W)) ^^ (length w+2-Suc m)"
      using wrap_forced_split[OF old_block[unfolded W_def] goodB old_whole[unfolded W_def]]
        order by (simp add: W_def)
    have lifted: "(wrap_flag_config False ?B,wrap_flag_config False ?D)
      ∈ (ktm_step (delta_ktm P)) ^^ (length w+2-Suc m)"
      using wrap_prefix_false_run[OF suffix] by (simp add: P_def)
    have total: "(init_config_ktm P (map Raw w),wrap_flag_config False ?D)
      ∈ (ktm_step (delta_ktm P)) ^^ (Suc m+(length w+2-Suc m))"
      using new_block lifted unfolding relpow_add by blast
    show ?thesis using total order by simp
  qed
qed

lemma wrap_prefix_short_reaches:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool" and N :: nat
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
      and k2: "2 ≤ k_ktm A"
      and pack: "⋀i. i*m < length w ⟹
        pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
      and short: "length w < m" "length w ≤ N"
  shows "reaches_state_in_time_ktm
    (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w)
    (False,if table w then t_ktm (encoding_wrap A pack m S)
      else r_ktm (encoding_wrap A pack m S)) (length w+2)"
proof -
  note run = wrap_prefix_short_run[where A=A and pack=pack and m=m and S=S and w=w
    and table=table and N=N, OF valid positive word blle k2 pack short]
  show ?thesis
    by (rule reaches_state_in_time_ktmI[OF _ relpow_Suc_I[OF run]]) simp_all
qed


subsection ‹Terminal states, transport and language›

text ‹The simulated machine's halting states are sinks of the wrap, and so
  of its patch.›

lemma wrap_run_terminal_sink:
  assumes valid: "valid_ktm A" and q: "q ∈ {t_ktm A, r_ktm A}"
  shows "(W_Run q, a, p, b, d) ∉ wrap_delta A pack m S"
proof
  assume member: "(W_Run q, a, p, b, d) ∈ wrap_delta A pack m S"
  have run: "(W_Run q, a, p, b, d) ∈ wrap_run_delta A S"
    by (rule wrap_delta_W_Run_source_only_run[OF member])
  obtain a0 p0 b0 d0 where source: "(q, a0, p0, b0, d0) ∈ delta_ktm A"
    using run unfolding wrap_run_delta_def by auto
  have "delta_ktm A ⊆
    (Q_ktm A - {t_ktm A, r_ktm A}) × (UNIV → Γ_ktm A) ×
    Q_ktm A × (UNIV → Γ_ktm A) × (UNIV → UNIV)"
    by (rule valid_ktm_delta_set[OF valid])
  with source q show False by auto
qed

lemma wrap_prefix_terminal_sink:
  fixes A :: "('q,'b) ktm"
  assumes valid: "valid_ktm A" and q: "q ∈ {t_ktm A, r_ktm A}"
      and state: "snd (ktc_state c) = W_Run q"
  shows "(c, y) ∉ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
proof
  assume "(c, y) ∈ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
  then obtain s ts n p' b d where src: "c = KConfig s ts n"
    and tuple: "(s, λj. ts j (n j), p', b, d) ∈ wrap_prefix_delta (encoding_wrap A pack m S) table N"
    by (cases rule: ktm_step.cases) auto
  obtain first q0 p where s: "s = (first, q0)"
    and old: "(q0, λj. ts j (n j), p, b, d) ∈ delta_ktm (encoding_wrap A pack m S)"
    using tuple unfolding wrap_prefix_delta_def by blast
  have "q0 = W_Run q" using state src s by simp
  then have "(W_Run q, λj. ts j (n j), p, b, d) ∈ wrap_delta A pack m S"
    using old by simp
  with wrap_run_terminal_sink[OF valid q] show False by blast
qed

text ‹On a long input the patch runs as the wrap does, so every
  simulation-phase state the wrap reaches the patch reaches in the same
  time, with the flag clear.›

lemma wrap_prefix_transport:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool" and N :: nat
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
      and k2: "2 ≤ k_ktm A"
      and pack: "⋀i. i*m < length w ⟹
        pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
      and long: "N < length w"
      and reach: "reaches_state_in_time_ktm (encoding_wrap A pack m S) (map Raw w) (W_Run q) T"
  shows "reaches_state_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w) (False, W_Run q) T"
proof -
  obtain k fin where k: "k ≤ T"
    and run: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), fin) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ k"
    and st: "ktc_state fin = W_Run q"
    using reach unfolding reaches_state_in_time_ktm_def by blast
  let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
  have old_whole: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), ?D)
      ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (length w + 2)"
    using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w
      and Σu=S, OF valid positive word blle k2 pack] by simp
  have goodD: "∀q. ktc_state ?D ≠ W_Run q" by (simp add: post_encoder_config_gen_def)
  have split: "length w + 2 ≤ k ∧
      (?D, fin) ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (k - (length w + 2))"
    using wrap_forced_split[OF old_whole goodD run] st by auto
  have new_prefix: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False ?D)
      ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (length w + 2)"
    by (rule wrap_prefix_long_prefix[where A=A and pack=pack and m=m and S=S and w=w and table=table and N=N, OF valid positive word blle k2 pack long])
  have lifted: "(wrap_flag_config False ?D, wrap_flag_config False fin)
      ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (k - (length w + 2))"
    using wrap_prefix_false_run split by blast
  have "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False fin)
      ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (length w + 2 + (k - (length w + 2)))"
    using new_prefix lifted unfolding relpow_add by blast
  moreover have eqk: "length w + 2 + (k - (length w + 2)) = k"
    using split[THEN conjunct1] by simp
  ultimately have whole: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False fin)
      ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ k"
    by (simp only: eqk)
  show ?thesis by (rule reaches_state_in_time_ktmI[OF k whole]) (simp add: st)
qed

text ‹On a short input every accepting run is the table's: the forced
  prefix ends in the redirected transition, whose target is a sink.›

lemma wrap_prefix_short_accepts:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool" and N :: nat
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
      and k2: "2 ≤ k_ktm A"
      and pack: "⋀i. i*m < length w ⟹
        pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
      and short: "length w < m" "length w ≤ N"
      and acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w) T"
  shows "table w"
proof -
  let ?C = "wrap_flag_config True (mid_buf_extending_config_gen (k_ktm A) A pack m w 0 (length w))"
  let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
  let ?q = "if table w then t_ktm (encoding_wrap A pack m S) else r_ktm (encoding_wrap A pack m S)"
  let ?fin = "KConfig (False, ?q) (ktc_tape ?D) (ktc_pos ?D)"
  note run = wrap_prefix_short_run[where A=A and pack=pack and m=m and S=S and w=w and table=table and N=N, OF valid positive word blle k2 pack short]
  obtain k E where accrun: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), E)
      ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ k"
    and stE: "ktc_state E = t_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N)"
    using acc unfolding accepts_in_time_ktm_iff_reaches reaches_state_in_time_ktm_def by blast
  have stE': "ktc_state E = (False, W_Run (t_ktm A))" using stE by simp
  have goodC: "∀q. snd (ktc_state ?C) ≠ W_Run q"
    by (simp add: mid_buf_extending_config_gen_def)
  have after: "(?C, E) ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (k - Suc (length w))"
    using wrap_prefix_forced_split[OF run(1) goodC accrun] stE' by auto
  obtain j where j: "k - Suc (length w) = Suc j"
  proof (cases "k - Suc (length w)")
    case 0
    then have "E = ?C" using after by simp
    then show ?thesis using stE' by simp
  next
    case (Suc j)
    then show ?thesis by (rule that)
  qed
  obtain Y where CY: "(?C, Y) ∈ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
    and YE: "(Y, E) ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ j"
    using relpow_Suc_D2[OF after[unfolded j]] by blast
  have Y: "Y = ?fin" by (rule wrap_prefix_step_unique[OF CY run(2) goodC])
  have sink: "(?fin, Z) ∉ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))" for Z
  proof (cases "table w")
    case True
    show ?thesis by (rule wrap_prefix_terminal_sink[OF valid, of "t_ktm A"]) (simp_all add: True)
  next
    case False
    show ?thesis by (rule wrap_prefix_terminal_sink[OF valid, of "r_ktm A"]) (simp_all add: False)
  qed
  have "E = ?fin"
  proof (cases j)
    case 0
    then show ?thesis using YE Y by simp
  next
    case (Suc i)
    then obtain Z where "(?fin, Z) ∈ ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))"
      using relpow_Suc_D2[OF YE[unfolded Y Suc]] by blast
    with sink show ?thesis by blast
  qed
  then have "?q = W_Run (t_ktm A)" using stE' by simp
  moreover have "r_ktm A ≠ t_ktm A" using valid by (cases A) auto
  ultimately show "table w" by (cases "table w") simp_all
qed

text ‹On a long input every accepting run of the patch passes through the
  wrap's post-encoder configuration with the flag clear, and from there it
  is a run of the wrap.›

lemma wrap_prefix_long_accepts:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b"
    and table :: "'a list ⇒ bool" and N :: nat
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and word: "set w ⊆ S" and blle: "bl_ktm A ≠ le_ktm A"
      and k2: "2 ≤ k_ktm A"
      and pack: "⋀i. i*m < length w ⟹
        pack (take m (drop (i*m) w)) ∈ Sigma_ktm A"
      and long: "N < length w"
      and acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w) T"
  shows "accepts_in_time_ktm (encoding_wrap A pack m S) (map Raw w) T"
proof -
  let ?D = "post_encoder_config_gen (k_ktm A) A pack m w"
  have new_prefix: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), wrap_flag_config False ?D)
      ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (length w + 2)"
    by (rule wrap_prefix_long_prefix[where A=A and pack=pack and m=m and S=S and w=w and table=table and N=N, OF valid positive word blle k2 pack long])
  have old_whole: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), ?D)
      ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (length w + 2)"
    using init_to_post_encoder_relpow[where M=A and pack=pack and c=m and w=w
      and Σu=S, OF valid positive word blle k2 pack] by simp
  obtain k E where k: "k ≤ T"
    and accrun: "(init_config_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N) (map Raw w), E) ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ k"
    and stE: "ktc_state E = t_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N)"
    using acc unfolding accepts_in_time_ktm_iff_reaches reaches_state_in_time_ktm_def by blast
  have stE': "ktc_state E = (False, W_Run (t_ktm A))" using stE by simp
  have goodD: "∀q. snd (ktc_state (wrap_flag_config False ?D)) ≠ W_Run q"
    by (simp add: post_encoder_config_gen_def)
  have split: "length w + 2 ≤ k ∧ (wrap_flag_config False ?D, E)
      ∈ (ktm_step (delta_ktm (wrap_prefix_patch (encoding_wrap A pack m S) table N))) ^^ (k - (length w + 2))"
    using wrap_prefix_forced_split[OF new_prefix goodD accrun] stE' by auto
  obtain E' where E: "E = wrap_flag_config False E'"
    and tail: "(?D, E') ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (k - (length w + 2))"
    using wrap_prefix_false_run_proj split by blast
  have "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), E')
      ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ (length w + 2 + (k - (length w + 2)))"
    using old_whole tail unfolding relpow_add by blast
  moreover have eqk: "length w + 2 + (k - (length w + 2)) = k"
    using split[THEN conjunct1] by simp
  ultimately have whole: "(init_config_ktm (encoding_wrap A pack m S) (map Raw w), E')
      ∈ (ktm_step (delta_ktm (encoding_wrap A pack m S))) ^^ k"
    by (simp only: eqk)
  have "ktc_state E' = t_ktm (encoding_wrap A pack m S)" using stE' E by simp
  then show ?thesis unfolding accepts_in_time_ktm_iff_reaches
    by (rule reaches_state_in_time_ktmI[OF k whole])
qed

text ‹With the wrap's own language as the table, the patch accepts the
  same user-facing language as the wrap.  No determinism is assumed.›

theorem wrap_prefix_language:
  fixes A :: "('q,'b) ktm" and pack :: "'a list ⇒ 'b" and N :: nat
  assumes valid: "valid_ktm A" and positive: "0 < m"
      and blle: "bl_ktm A ≠ le_ktm A" and k2: "2 ≤ k_ktm A"
      and width: "N < m"
      and enc: "⋀w. set w ⊆ S ⟹ set (wrap_enc pack m w) ⊆ Sigma_ktm A"
  shows "Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) = Lang_user_wrap (encoding_wrap A pack m S)"
proof (rule set_eqI)
  fix w
  have legal: "set (map Raw w) ⊆ Raw ` S ⟷ set w ⊆ S" by auto
  have tP: "t_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) = (False, W_Run (t_ktm A))" by simp
  show "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) ⟷ w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
  proof (cases "set w ⊆ S")
    case False
    then have badW: "¬ set (map Raw w) ⊆ Sigma_ktm (encoding_wrap A pack m S)"
      and badP: "¬ set (map Raw w) ⊆ Sigma_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)" by auto
    have "map Raw w ∉ Lang_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)" and "map Raw w ∉ Lang_ktm (encoding_wrap A pack m S)"
      using badW badP unfolding Lang_ktm_iff by blast+
    then show ?thesis by (simp add: Lang_user_wrap_def)
  next
    case word: True
    have packw: "pack (take m (drop (i*m) w)) ∈ Sigma_ktm A" if "i*m < length w" for i
      using enc[OF word] pack_take_in_set_wrap_enc[OF positive that, where pack=pack] by blast
    show ?thesis
    proof (cases "length w ≤ N")
      case short: True
      have shortm: "length w < m" using short width by simp
      show ?thesis
      proof
        assume "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
        then obtain T where acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) T"
          by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
        show "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
          by (rule wrap_prefix_short_accepts[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
              OF valid positive word blle k2 packw shortm short acc])
      next
        assume member: "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
        have "reaches_state_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w)
            (False, W_Run (t_ktm A)) (length w + 2)"
          using wrap_prefix_short_reaches[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
              OF valid positive word blle k2 packw shortm short] member by simp
        then have "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) (length w + 2)"
          unfolding accepts_in_time_ktm_iff_reaches tP .
        then show "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
          using word legal by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
      qed
    next
      case long: False
      have longN: "N < length w" using long by simp
      show ?thesis
      proof
        assume "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
        then obtain T where acc: "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) T"
          by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
        have "accepts_in_time_ktm (encoding_wrap A pack m S) (map Raw w) T"
          by (rule wrap_prefix_long_accepts[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
              OF valid positive word blle k2 packw longN acc])
        then show "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
          using word legal by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
      next
        assume "w ∈ Lang_user_wrap (encoding_wrap A pack m S)"
        then obtain T where acc: "accepts_in_time_ktm (encoding_wrap A pack m S) (map Raw w) T"
          by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
        have reach: "reaches_state_in_time_ktm (encoding_wrap A pack m S) (map Raw w) (W_Run (t_ktm A)) T"
          using acc unfolding accepts_in_time_ktm_iff_reaches by simp
        have "reaches_state_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) (False, W_Run (t_ktm A)) T"
          by (rule wrap_prefix_transport[where A=A and pack=pack and m=m and S=S and w=w and table="λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)" and N=N,
              OF valid positive word blle k2 packw longN reach])
        then have "accepts_in_time_ktm (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N) (map Raw w) T"
          unfolding accepts_in_time_ktm_iff_reaches tP .
        then show "w ∈ Lang_user_wrap (wrap_prefix_patch (encoding_wrap A pack m S) (λu. u ∈ Lang_user_wrap (encoding_wrap A pack m S)) N)"
          using word legal by (auto simp: Lang_user_wrap_def Lang_ktm_iff)
      qed
    qed
  qed
qed

end