Theory Wrap_Band_Speedup

theory Wrap_Band_Speedup
  imports Wrap_Convention Wrap_Speedup_Arithmetic
begin

section ‹First-block speedup above a linear band›

text ‹The machine here is the wrap with its first-block language table.  The
  table decides short inputs within the convention's floor; long inputs follow
  the raw wrap at the same cost.  The table is a finite restriction of the
  source language, so the machine is shown to exist rather than computed from
  the source.

  The timing conclusion gives a bounded accepting run for each word in the
  language, and says nothing about rejecting runs.  On a short word the machine
  stops with the table's verdict, so a nondeterministic source that both
  accepts and rejects that word along different runs keeps only its accepting
  verdict.  On long inputs every simulated run is carried over, so a statement
  about the time to reject needs its own argument about how the source's runs
  end.›

abbreviation wrap_speedup ::
  "nat ⇒ ('q, 'a) ktm ⇒
    (('q × 'a ae_stage, 'a, nat ⇒ 'a) wrap_state,
      ('a, nat ⇒ 'a) wrap_alphabet) ktm" where
  "wrap_speedup m M ≡ encoding_wrap
    (alphabet_enlarge m M) (ae_pack m (bl_ktm M)) (m) (Sigma_ktm M)"

definition wrap_speedup_bound :: "nat ⇒ nat ⇒ nat ⇒ nat" where
  "wrap_speedup_bound m n T = n + 3 * ((n + m - 1) div m) +
    8 * ((T + m - 1) div m) + 9"

abbreviation wrap_prefix_speedup ::
  "nat ⇒ ('q,'a) ktm ⇒ nat ⇒
    (bool × (('q × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
      ('a,nat ⇒ 'a) wrap_alphabet) ktm" where
  "wrap_prefix_speedup m M N ≡
    wrap_prefix_patch (wrap_speedup m M) (λw. w ∈ Lang_ktm M) N"

definition wrap_prefix_speedup_bound where
  "wrap_prefix_speedup_bound N m n T = (if n ≤ N then n+2 else wrap_speedup_bound m n T)"

lemma wrap_prefix_speedup_contract:
  fixes M :: "('s,'a) ktm"
    and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
      ('a,nat ⇒ 'a) wrap_alphabet) ktm"
  assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
      and width: "N < m"
  defines "P ≡ wrap_prefix_speedup m M N"
  shows "valid_ktm P"
    and "Lang_ktm P = map Raw ` Lang_ktm M"
    and "det_ktm M ⟹ det_ktm P"
proof -
  have m_pos: "0 < m" using width by linarith
  let ?m = "m"
  let ?A = "alphabet_enlarge m M :: ('s × 'a ae_stage,nat ⇒ 'a) ktm"
  let ?pack = "ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a)"
  let ?W = "encoding_wrap ?A ?pack ?m (Sigma_ktm M)"
  have validM: "valid_ktm M" and blle: "le_ktm M ≠ bl_ktm M" using wf by auto
  have validA: "valid_ktm ?A" by (rule alphabet_enlarge_wf[OF validM m_pos])
  have positive: "0 < ?m" by (rule m_pos)
  have blleA: "bl_ktm ?A ≠ le_ktm ?A"
    using LE_block_neq_bl_block[OF m_pos blle]
    by (metis bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge)
  have k2A: "2 ≤ k_ktm ?A" using k2 by (cases M) (simp add: alphabet_enlarge_def)
  note F = linear_speedup_form_1_raw_nae[OF wf k2 m_pos]
  show "valid_ktm P" unfolding P_def by (rule wrap_prefix_patch_valid[OF F(1)])
  have enc: "set (wrap_enc ?pack ?m w) ⊆ Sigma_ktm ?A"
    if "set w ⊆ Sigma_ktm M" for w
    by (rule ae_wrap_enc_in_Sigma[OF validM that m_pos])
  have table: "(λu. u ∈ Lang_ktm M) = (λu. u ∈ Lang_user_wrap ?W)"
    using F(2) by simp
  have lang: "Lang_user_wrap P = Lang_ktm M"
  proof -
    have "Lang_user_wrap P = Lang_user_wrap ?W"
      unfolding P_def table
      by (rule wrap_prefix_language[OF validA positive blleA k2A width enc])
    then show ?thesis using F(2) by simp
  qed
  show "Lang_ktm P = map Raw ` Lang_ktm M"
  proof
    show "Lang_ktm P ⊆ map Raw ` Lang_ktm M"
    proof
      fix v assume member: "v ∈ Lang_ktm P"
      then have "set v ⊆ Raw ` Sigma_ktm M"
        by (simp add: P_def Lang_ktm_iff)
      then have "v ∈ lists (Raw ` Sigma_ktm M)" by (auto simp: in_lists_conv_set)
      then obtain w where v: "v = map Raw w" by (auto simp: lists_image)
      have "w ∈ Lang_user_wrap P"
        unfolding Lang_user_wrap_def mem_Collect_eq using member unfolding v .
      then show "v ∈ map Raw ` Lang_ktm M" using lang v by blast
    qed
    show "map Raw ` Lang_ktm M ⊆ Lang_ktm P"
      using lang unfolding Lang_user_wrap_def by blast
  qed
  assume det: "det_ktm M"
  have "det_ktm ?W"
    by (rule linear_speedup_form_1_raw_dae(2)[OF wf det k2 m_pos])
  then show "det_ktm P" unfolding P_def by (rule wrap_prefix_patch_det)
qed

lemma wrap_prefix_speedup_short:
  fixes M :: "('s,'a) ktm"
    and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
      ('a,nat ⇒ 'a) wrap_alphabet) ktm"
  assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
      and width: "N < m"
      and word: "set w ⊆ Sigma_ktm M" and short: "length w ≤ N"
  defines "P ≡ wrap_prefix_speedup m M N"
  shows "reaches_state_in_time_ktm P (map Raw w)
    (if w ∈ Lang_ktm M then t_ktm P else r_ktm P) (length w + 2)"
proof -
  have m_pos: "0 < m" using width by linarith
  let ?m = "m"
  let ?A = "alphabet_enlarge m M :: ('s × 'a ae_stage,nat ⇒ 'a) ktm"
  let ?pack = "ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a)"
  let ?W = "encoding_wrap ?A ?pack ?m (Sigma_ktm M)"
  have validM: "valid_ktm M" and blle: "le_ktm M ≠ bl_ktm M" using wf by auto
  have validA: "valid_ktm ?A" by (rule alphabet_enlarge_wf[OF validM m_pos])
  have positive: "0 < ?m" by (rule m_pos)
  have blleA: "bl_ktm ?A ≠ le_ktm ?A"
    using LE_block_neq_bl_block[OF m_pos blle]
    by (metis bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge)
  have k2A: "2 ≤ k_ktm ?A" using k2 by (cases M) (simp add: alphabet_enlarge_def)
  have pack: "?pack (take ?m (drop (i*?m) w)) ∈ Sigma_ktm ?A"
    if "i*?m < length w" for i
    using ae_wrap_enc_in_Sigma[OF validM word m_pos]
      pack_take_in_set_wrap_enc[OF positive that, where pack="?pack"] by blast
  have shortm: "length w < ?m" using short width by arith
  have run: "reaches_state_in_time_ktm P (map Raw w)
    (False, if w ∈ Lang_ktm M then t_ktm ?W else r_ktm ?W) (length w + 2)"
    unfolding P_def
    by (rule wrap_prefix_short_reaches[where A="?A" and pack="?pack" and m="?m"
      and S="Sigma_ktm M" and w=w and table="λu. u ∈ Lang_ktm M" and N=N,
      OF validA positive word blleA k2A pack shortm short])
  show ?thesis using run by (cases "w ∈ Lang_ktm M") (simp_all add: P_def)
qed

lemma wrap_prefix_speedup_long:
  fixes M :: "('s,'a) ktm"
    and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
      ('a,nat ⇒ 'a) wrap_alphabet) ktm"
  assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
      and word: "set w ⊆ Sigma_ktm M" and long: "N < length w"
      and run: "reaches_state_in_time_ktm (wrap_speedup m M) (map Raw w) (W_Run q) T"
      and m_pos: "0 < m"
  defines "P ≡ wrap_prefix_speedup m M N"
  shows "reaches_state_in_time_ktm P (map Raw w) (False, W_Run q) T"
proof -
  let ?m = "m"
  let ?A = "alphabet_enlarge m M :: ('s × 'a ae_stage,nat ⇒ 'a) ktm"
  let ?pack = "ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a)"
  have validM: "valid_ktm M" and blle: "le_ktm M ≠ bl_ktm M" using wf by auto
  have validA: "valid_ktm ?A" by (rule alphabet_enlarge_wf[OF validM m_pos])
  have positive: "0 < ?m" by (rule m_pos)
  have blleA: "bl_ktm ?A ≠ le_ktm ?A"
    using LE_block_neq_bl_block[OF m_pos blle]
    by (metis bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge)
  have k2A: "2 ≤ k_ktm ?A" using k2 by (cases M) (simp add: alphabet_enlarge_def)
  have pack: "?pack (take ?m (drop (i*?m) w)) ∈ Sigma_ktm ?A"
    if "i*?m < length w" for i
    using ae_wrap_enc_in_Sigma[OF validM word m_pos]
      pack_take_in_set_wrap_enc[OF positive that, where pack="?pack"] by blast
  show ?thesis unfolding P_def
    by (rule wrap_prefix_transport[where A="?A" and pack="?pack" and m="?m"
      and S="Sigma_ktm M" and w=w and table="λu. u ∈ Lang_ktm M" and N=N,
      OF validA positive word blleA k2A pack long run])
qed

lemma wrap_prefix_speedup_accepts:
  fixes M :: "('s,'a) ktm"
    and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
      ('a,nat ⇒ 'a) wrap_alphabet) ktm"
  assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
      and width: "N < m"
      and word: "set w ⊆ Sigma_ktm M"
      and source: "accepts_in_time_ktm M w T"
  defines "P ≡ wrap_prefix_speedup m M N"
  shows "accepts_in_time_ktm P (map Raw w)
    (wrap_prefix_speedup_bound N (m) (length w) T)"
proof (cases "length w ≤ N")
  case True
  have member: "w ∈ Lang_ktm M" using word source by (auto simp: Lang_ktm_iff)
  have run: "reaches_state_in_time_ktm P (map Raw w)
    (if w ∈ Lang_ktm M then t_ktm P else r_ktm P) (length w + 2)"
    unfolding P_def by (rule wrap_prefix_speedup_short[OF wf k2 width word True])
  show ?thesis using run member True
    by (simp add: accepts_in_time_ktm_iff_reaches wrap_prefix_speedup_bound_def)
next
  case False
  have m_pos: "0 < m" using width by linarith
  let ?m = "m"
  let ?W = "wrap_speedup m M :: (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state,
      ('a,nat ⇒ 'a) wrap_alphabet) ktm"
  have long: "N < length w" using False by simp
  have raw: "accepts_in_time_user_wrap ?W w
    (length w + (length w + ?m - 1) div ?m + 5
      + 2 * ((length w + ?m - 1) div ?m) + 8 * ((T + ?m - 1) div ?m) + 4)"
    using linear_speedup_form_1_raw_nae(3)[where T="λ_. T",
      OF wf k2 m_pos] word source by blast
  have run: "reaches_state_in_time_ktm ?W (map Raw w)
    (W_Run (t_ktm M, init_stage m (le_ktm M))) (wrap_speedup_bound ?m (length w) T)"
    using raw by (simp add: accepts_in_time_user_wrap_def accepts_in_time_ktm_iff_reaches
      t_ktm_alphabet_enlarge wrap_speedup_bound_def algebra_simps)
  have "reaches_state_in_time_ktm P (map Raw w)
    (False, W_Run (t_ktm M, init_stage m (le_ktm M))) (wrap_speedup_bound ?m (length w) T)"
    unfolding P_def by (rule wrap_prefix_speedup_long[OF wf k2 word long run m_pos])
  then show ?thesis using False
    by (simp add: P_def accepts_in_time_ktm_iff_reaches
      t_ktm_alphabet_enlarge wrap_prefix_speedup_bound_def)
qed

lemma wrap_prefix_speedup_bound_band:
  assumes q: "0 < q"
      and width: "16 * (3 + 8*c) * (q+1) + 16*c + 1 ≤ m"
      and band: "⋀n. N0 ≤ n ⟹ n + n div q ≤ t n"
  shows "wrap_prefix_speedup_bound (max N0 (q * (81 + 128*e))) m n (c*t n+e)
    ≤ max (n+2) (t n)"
proof (cases "n ≤ max N0 (q * (81 + 128*e))")
  case True then show ?thesis by (simp add: wrap_prefix_speedup_bound_def)
next
  case False
  have far: "N0 ≤ n" and big: "q * (81 + 128*e) ≤ n" using False by auto
  have "n + (n+m-1) div m + 5 + 2*((n+m-1) div m)
    + 8*((c*t n+e+m-1) div m) + 4 ≤ t n"
    by (rule speedup_band_arith[OF q width big band[OF far]])
  then show ?thesis using False
    by (simp add: wrap_prefix_speedup_bound_def wrap_speedup_bound_def algebra_simps)
qed

theorem wrap_prefix_speedup_band:
  fixes M :: "('s,'a) ktm"
    and P :: "(bool × (('s × 'a ae_stage,'a,nat ⇒ 'a) wrap_state),
      ('a,nat ⇒ 'a) wrap_alphabet) ktm"
  assumes wf: "well_formed_ktm M" and k2: "2 ≤ k_ktm M"
      and timed: "⋀w. w ∈ Lang_ktm M ⟹
        accepts_in_time_ktm M w (c * t (length w) + e)"
      and q: "0 < q"
      and band: "⋀n. N0 ≤ n ⟹ n + n div q ≤ t n"
      and large: "16 * (3 + 8*c) * (q+1) + 16*c + 1 ≤ m"
      and width: "max N0 (q * (81 + 128*e)) < m"
  defines "P ≡ wrap_prefix_speedup m M (max N0 (q * (81 + 128*e)))"
  shows "time_bounded_conv P t"
proof -
  have lang: "Lang_ktm P = map Raw ` Lang_ktm M"
    unfolding P_def by (rule wrap_prefix_speedup_contract(2)[OF wf k2 width])
  show ?thesis unfolding time_bounded_conv_def
  proof
    fix v assume "v ∈ Lang_ktm P"
    then obtain w where v: "v = map Raw w" and member: "w ∈ Lang_ktm M"
      using lang by blast
    have word: "set w ⊆ Sigma_ktm M" using member by (simp add: Lang_ktm_iff)
    have run: "accepts_in_time_ktm P (map Raw w)
      (wrap_prefix_speedup_bound (max N0 (q * (81 + 128*e)))
        (m) (length w) (c*t (length w)+e))"
      unfolding P_def by (rule wrap_prefix_speedup_accepts[OF wf k2 width word timed[OF member]])
    have "accepts_in_time_ktm P (map Raw w) (max (length w+2) (t (length w)))"
      by (rule accepts_in_time_ktm_mono[OF run wrap_prefix_speedup_bound_band[OF q large band]])
    then show "accepts_in_time_ktm P v (max (length v+2) (t (length v)))"
      by (simp add: v)
  qed
qed

end